2912. 放书

cd106224

dfs加剪枝

#include <iostream>
#include <string.h>
using namespace std;
int b[11];
int n;
int ans;
int res1;
int res;
void DFS(int index, int sum, int mul, int) {
    if (sum > 55) {
        return;
    }
    if (index == n) {
        if (sum == res1 && mul == res) {
            for (int i = 1; i <= n; ++i) {
                if (b[i] == i) {
                    return;
                }
            }
            ans++;
            if (n < 8) {
                for (int i = 1; i < n; ++i) {
                    cout << b[i];
                }
                cout << b[n] << endl;
            }
        }
        return;
    }
    for (int i = 1; i <= n; ++i) {
        bool isgo = false;
        for (int j = 1; j <= index; ++j) {
            if (b[j] == i) {
                isgo = true;
            }
        }
        if (isgo) {
            continue;
        }
        DFS(index + 1, sum + i, mul*i, b[index + 1] = i);
    }
}



int main() {
    int num;
    cin >> num;
    for (int k = 0; k < num; ++k) {
        ans = 0;
        res = 1;
        memset(b, 0, sizeof(b));
        cin >> n;
        res1 = n * (n + 1) / 2;
        for (int i = 1; i <= n; ++i) {
            res = res * i;
        }
        DFS(0, 0, 1, 0);
        if (n >= 8) {
            cout << ans << endl;
        }
    }
    return 0;
}
Qiubaby

include

include

include

using namespace std;
int n;
vectorv;
int flag[11]= {0};
int ans=0;
void dfs(int i) {
if(i==n+1) {
ans++;
if(n<8) {
for(int j = 0; j < v.size(); j++)
cout<>t;
while(t–) {
cin>>n;
ans=0;
dfs(1);
if(n>=8)
cout<<ans<<endl;
}
return 0;
}

Qiubaby

全排列也可

你当前正在回复 博客/题目
存在问题!