poj 3181 Dollar Dayz

题目大意:

N由 1到K的数组成，求这样的组成方式有多少种？

Input

A single line with two space-separated integers: N and K.

Output

A single line with a single integer that is the number of unique ways FJ can spend his money.

Sample Input

5 3

Sample Output

5

用动态规划来解此题
dp[i][j]表示前i个数构成j的方法数
若j < i
则dp[i][j] = dp[i-1][j]
否则
dp[i][j] = dp[i][j-i] + dp[i-1][j]

还可以简化为一维数组
代码如下

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 int dp[1002];
 5 
 6 int main(int argc, char const *argv[])
 7 {
 8     int n, k;
 9     scanf("%d %d",&n,&k);
10     memset(dp, 0, sizeof(dp));
11     dp[0] = 1;
12     for(int i = 1; i <= k; i++) {
13         for(int j = i; j <= n; j++) {
14             dp[j] = dp[j] + dp[j-i];
15         }
16     }
17     printf("%d
",dp[n]);
18     return 0;
19 }

但提交错误，考虑到数值太大溢出，只好模拟大整数的加法

设一位代表5位

那么int dp[1002][20]每一个数可以最多有100位，代码如下

 1 #include <cstdio>
 2 #include <cstring>
 3 #define base 100000
 4 
 5 int dp[1002][20];
 6 
 7 void add(int a, int b) {
 8     int ci = 0;
 9     for(int i = 0; i < 20; i++) {
10         int ben = dp[a][i] + dp[b][i] + ci;
11         dp[a][i] = ben % base;
12         ci = ben/base;
13     }
14 }
15 
16 void show(int n) {
17     bool isF = true;
18     for(int i = 19; i >= 0; i--) {
19         if(isF && dp[n][i] != 0) {
20             isF = false;
21             printf("%d",dp[n][i]);//第一个不用凑够5位
22         }
23         else if(!isF) {
24             printf("%05d",dp[n][i]);//注意要凑够5位，不够前面补0
25         }
26     }
27     puts("");
28 }
29 int main(int argc, char const *argv[])
30 {
31     int n, k;
32     scanf("%d %d",&n,&k);
33         memset(dp, 0, sizeof(dp));
34         dp[0][0] = 1;
35         for(int i = 1; i <= k; i++) {
36             for(int j = i; j <= n; j++) {
37                 add(j, j-i);
38             }
39         }
40         show(n);
41     
42     
43     return 0;
44 }