档案信息网站建设,更改wordpress前缀,现实有有哪里学做网站的,php mysql网站开发实例目录 [NOIP2001 提高组] 数的划分题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 动态规划的解题思路Code运行结果DFSCode运行结果 [NOIP2001 提高组] 数的划分
题目描述
将整数 n n n 分成 k k k 份#xff0c;且每份不能为空#xff0c;任意两个方案不相… 目录 [NOIP2001 提高组] 数的划分题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 动态规划的解题思路Code运行结果DFSCode运行结果 [NOIP2001 提高组] 数的划分
题目描述
将整数 n n n 分成 k k k 份且每份不能为空任意两个方案不相同不考虑顺序。
例如 n 7 n7 n7 k 3 k3 k3下面三种分法被认为是相同的。 1 , 1 , 5 1,1,5 1,1,5; 1 , 5 , 1 1,5,1 1,5,1; 5 , 1 , 1 5,1,1 5,1,1.
问有多少种不同的分法。
输入格式 n , k n,k n,k 6 n ≤ 200 6n \le 200 6n≤200 2 ≤ k ≤ 6 2 \le k \le 6 2≤k≤6
输出格式 1 1 1 个整数即不同的分法。
样例 #1
样例输入 #1
7 3样例输出 #1
4提示
四种分法为 1 , 1 , 5 1,1,5 1,1,5; 1 , 2 , 4 1,2,4 1,2,4; 1 , 3 , 3 1,3,3 1,3,3; 2 , 2 , 3 2,2,3 2,2,3.
【题目来源】
NOIP 2001 提高组第二题
动态规划的解题思路
动态规划相当于把n个小球放到k个箱子里面问有几种分法。dp[i][j]相当于把第i个小球放到第j个箱子里。状态初始化dp[i][1] 1状态转移方程dp[i][j] dp[i - 1][j - 1] dp[i - j][j]
Code
#includeiostreamusing namespace std;int n, k;
int dp[210][10];int main() {cin n k;for (int i 0; i n; i) {dp[i][1] 1; // 状态初始化}for (int i 1; i n; i) {for (int j 2; j k; j) {if (i j) {dp[i][j] dp[i - 1][j - 1] dp[i - j][j];}}}cout dp[n][k] endl;return 0;
}
运行结果 DFS
Code
#includeiostreamusing namespace std;int ans;void dfs(int m, int k, int n) {if (k 1) {ans;return;}for (int i m; i n / k; i) {dfs(i, k - 1, n - i);}
}int main() {int n, k;cin n k;dfs(1, k, n);cout ans;return 0;
}
运行结果
