Items divided

题目链接：http://acm.xidian.edu.cn/problem.php?id=1183

参考：http://www.cnblogs.com/wanghetao/archive/2013/11/25/3442192.html

划分数（dp）

以前划分数没仔细看，拿到这题的时候随便弄了个dp，调了半个多小时，结束后游少提醒转移方程是错的= =

dp[i][j]表示将i划分成j个正整数的划分数，之后有以下三种情况：

1.i<j 此时i不可能划分成j个正整数，故dp[i][j]=0;

2.i==j 此时只有一种情况（将i划分成j个1），故dp[i][j]=1;

3.i>j 此时根据含不含1可分成（1和j-1个正整数）或（j个不含1的正整数）

即dp[i-1][j-1]或dp[i-j][j]，故dp[i][j]=dp[i-1][j-1]+dp[i-j][j].

这题询问的次数有点多，直接求会TLE，所以我先打了张ans的表。

代码如下：

 1 #include<cstdio>
 2 #define N 1001
 3 #define Mod (long long)(1e9+7)
 4 using namespace std;
 5 typedef long long LL;
 6 LL n,m;
 7 LL dp[N][N];
 8 LL ans[N][N];
 9 int main(void){
10     for(int i=1;i<=1000;++i)dp[i][1]=1;
11     for(int j=2;j<=1000;++j)
12     for(int i=1;i<=1000;++i){
13         if(i==j)dp[i][j]=1;
14         else if(i>j)dp[i][j]=(dp[i-1][j-1]+dp[i-j][j])%Mod;
15     }
16     for(int i=1;i<=1000;++i)
17     for(int j=1;j<=1000;++j)
18         ans[i][j]=(ans[i][j-1]+dp[i][j])%Mod;
19     while(scanf("%lld%lld",&n,&m)){
20         if(n==0&&m==0)break;
21         printf("%lld
",ans[n][m]);
22     }
23 }