题目链接:https://www.luogu.com.cn/problem/P1118
中文题面
想法:
当然是先暴力一发了。
然后就可以优化暴力代码了:
#include <algorithm> #include <string> #include <string.h> #include <vector> #include <map> #include <stack> #include <set> #include <queue> #include <math.h> #include <cstdio> #include <iomanip> #include <time.h> #include <bitset> #include <cmath> #include <sstream> #include <iostream> #include <cstring> #define LL long long #define ls nod<<1 #define rs (nod<<1)+1 #define pii pair<int,int> #define mp make_pair #define pb push_back const double eps = 1e-10; const int maxn = 5 + 10; const LL mod = 1e9 + 7; const LL INF = 1e18; int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;} using namespace std; int n,sum; int a[maxn],vis[maxn]; int c[maxn][maxn]; bool flag; inline void dfs(int x,int s) { if (s > sum) return ; if (x == n+1) { if (s == sum) { flag = true; return ; } return ; } for (int i = 1;i <= n;i++) { if (!vis[i]) { vis[i] = 1; a[x] = i; dfs(x+1,s+i*c[n][x]); if (flag) return ; vis[i] = 0; } } } int main() { cin >> n >> sum; c[1][1] = 1; for (int i = 2;i <= n;i++) { for (int j = 1;j <= i;j++) c[i][j] = c[i-1][j-1]+c[i-1][j]; } flag = false; dfs(1,0); if (flag) { for (int i = 1;i <= n;i++) cout << a[i] << " "; cout << "\n"; } return 0; }