2011-08-17 10:17:16Morris

d855. NOIP2001 2.数的划分

d855. NOIP2001 2.数的划分

內容 :

  将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。
  例如:n=7,k=3,下面三种分法被认为是相同的。
  115 151 511
  问有多少种不同的分法。

輸入說明 :

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)

效率可能有點差就是了
/**********************************************************************************/
/*  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;
}