Loading... 曾经的我，为这道题挠头。今非昔比。 --- [P1025 数的划分](https://www.luogu.com.cn/problem/P1025) 正解是DP。由于数据比较小，也可以使用DFS加一点点剪枝。 ## DFS 从0开始累加，同时记录累加次数和上一次累加的数以防止方案重复。当sum == n且s == k时，方案数+1。 一定要剪枝！ ```cpp #include <cstdio> int n, k; int dfs(int sum, int s, int last){ if(sum == n && s == k) return 1; if(s >= k) return 0; int ans = 0; for(int i = last; sum+i+k-s-1 <= n; ++i){ ans += dfs(sum+i, s+1, i); } return ans; } int main(){ scanf("%d%d", &n, &k); printf("%d\n", dfs(0, 0, 1)); return 0; } ``` ## DP f[x][i]表示将x分成i份的方案数，则f[x][1] = 1。可以得到状态转移方程： $$ f[x][i] = f[x-1][i-1]+f[x-i][i] $$ 代码实现非常简单。需要注意：要判断x >= i，否则状态不存在；因为已经处理了f[x][1] = 1，所以i是从2开始的。 ```cpp #include <cstdio> int n, k, f[201][7]; int main(){ scanf("%d%d", &n, &k); for(int i = 1; i <= n; ++i){ f[i][1] = 1; } for(int x = 1; x <= n; ++x){ for(int i = 2; i <= k; ++i){ if(x >= i) f[x][i] = f[x-1][i-1]+f[x-i][i]; } } printf("%d\n", f[n][k]); return 0; } ``` © 允许规范转载 赞赏 如果我的文章对你有用，请随意赞赏 赞赏作者 微信
1 条评论
写的太好了！