求助 用回溯法只拿了30分
查看原帖
求助 用回溯法只拿了30分
1418426
HeKaBi楼主2024/8/30 11:27
#include <bits/stdc++.h>
#define int long long
using namespace std;
int counts = 0;
vector<int> path;

bool dfs(vector<int> &temp, vector<bool> &used, int m)
{
    if (path.size() == temp.size())
    {
        counts++;
        if (counts >= m + 1)
            return true;
        return false;
    }
    for (int i = 0; i < temp.size(); i++)
    {
        if (used[i] == true)
            continue;
        used[i] = true;
        path.push_back(temp[i]);
        if (dfs(temp, used, m))
            return true;
        path.pop_back();
        used[i] = false;
    }
    return false;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    int len;
    if (m + 1 <= 2)
        len = 2;
    else if (m + 1 <= 6)
        len = 3;
    else if (m + 1 <= 24)
        len = 4;
    else if (m + 1 <= 120)
        len = 5;
    vector<int> nums(n);
    vector<int> temp(len);
    int index = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
        if (i >= n - len)
            temp[index++] = nums[i];
    }
    vector<bool> used(len, false);
    dfs(temp, used, m);
    for (int i = 0; i < n - len; i++)
    {
        cout << nums[i] << " ";
    }
    for (int i = 0; i < path.size(); i++)
    {
        cout << path[i] ;
        if(i<path.size()-1)
            cout << " ";
    }
    cout << '\n';
    return 0;
}
2024/8/30 11:27
加载中...