2011-08-17 10:17:16Morris
d855. NOIP2001 2.数的划分
d855. NOIP2001 2.数的划分
內容 :
将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。
例如:n=7,k=3,下面三种分法被认为是相同的。
1,1,5; 1,5,1; 5,1,1;
问有多少种不同的分法。
例如:n=7,k=3,下面三种分法被认为是相同的。
1,1,5; 1,5,1; 5,1,1;
问有多少种不同的分法。
輸入說明 :
n,k (6<n≤200,2≤k≤6)
輸出說明 :
一个整数,即不同的分法。
範例輸入 :
7 3
範例輸出 :
4
提示 :
出處 :
NOIP2001提高组第二题 (管理:liouzhou_101)
作法 : DP
DP[k][n][s]
分幾堆 k, 總和 n, 最大數字 s
推導得 DP[k+1][n+a][a] += DP[k][n][s] (a ≧ s)
記得要初始值 DP[1][a][a] = 1 (for all a)
效率可能有點差就是了
/**********************************************************************************/作法 : DP
DP[k][n][s]
分幾堆 k, 總和 n, 最大數字 s
推導得 DP[k+1][n+a][a] += DP[k][n][s] (a ≧ s)
記得要初始值 DP[1][a][a] = 1 (for all a)
效率可能有點差就是了
/* Problem: d855 "NOIP2001 2.数的划分" from NOIP2001提高组第二题 */
/* Language: C */
/* Result: AC (9ms, 1161KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-17 10:09:22 */
/**********************************************************************************/
#include<stdio.h>
int DP[7][201][201] = {};
main() {
int a, b, c, d;
DP[1][1][1] = 1;
for(a = 1; a <= 5; a++) {
for(b = 1; b <= 200; b++) {
DP[1][b][b] = 1;
for(c = 1; c <= b; c++)
for(d = c; b+d <= 200; d++) {
DP[a+1][b+d][d] += DP[a][b][c];
}
}
}
int n, k, sum;
while(scanf("%d %d", &n, &k) == 2) {
sum = 0;
for(a = 0; a <= 200; a++)
sum += DP[k][n][a];
printf("%d\n", sum);
}
return 0;
}