DP训练1009

http://acm.hdu.edu.cn/webcontest/contest_show.php?cid=3404 DP专题训练

一道整数划分的题目

将M个蛋糕放在N个盘子里面

当M>N时，可以先在每个盘子里面放一个蛋糕，剩下M-N的蛋糕放在N个盘子里面，也可以腾出一个盘子来，用剩下的盘子放M的蛋糕，则f(N,M)=f(N,M-N)+f(N-1,M);

当M=N时，可以每个盘子放一个蛋糕，也可以空闲一个盘子，则f(N,M) = f(N-1,M) + 1;

当M< N 时，肯定会空盘子，则f(N,M) = f(N-1,M);

代码如下：

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 const int maxn = 5000;
 6 int dp[2][maxn];
 7 const int mod = 1000000007;
 8 
 9 /*int solve(int n,int m)
10 {
11     if(n == 0) return 0;
12     if(m == 1) return 1;
13     if(n > m) return solve(n-1,m) % mod;
14     else if(n == m) return (solve(n-1,m) + 1) % mod;
15     else return (solve(n,m-n) + solve(n-1,m))%mod;
16 }*/
17 
18 int main()
19 {
20     int n,m;
21     while(cin >> n >> m)
22     {
23         memset(dp,0,sizeof(dp));
24 
25         //cout << solve(n,m) % mod << endl;
26         for(int i = 1;i <= n;i ++)
27         {
28             for(int j = 1;j <= m;j ++)
29             {
30                 int k = i % 2;
31                 if(j > i) dp[k][j] = dp[k][j-i] + dp[1-k][j];
32                 else if(j == i) dp[k][j] = 1 + dp[1-k][j];
33                 else dp[k][j] = dp[1-k][j];
34                 dp[k][j] %= mod;
35             }
36         }
37 
38         cout << dp[n%2][m]%mod << endl;
39     }
40 
41     return 0;
42 }