UESTC--1732

原题链接：http://acm.uestc.edu.cn/problem.php?pid=1732

分析：dp,n个相同物品放入m个相同的盒子(允许为空)的个数为dp[n][m]=dp[n][m-1]+dp[n-m][m];

dp[n][m-1]表示有空盒的情况，dp[n-m][m]表示没有空盒的情况。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define maxn 101
 7 #define mod 1000007
 8 using namespace std;
 9 int dp[maxn][maxn];
10 void solve()
11 {
12     for(int i=1;i<=100;i++)
13     {
14         dp[i][1]=1;dp[1][i]=1;
15     }
16     for(int i=2;i<=100;i++)
17     for(int j=2;j<=100;j++)
18     {
19         if(i>j)
20         dp[i][j]=(dp[i][j-1]+dp[i-j][j])%mod;
21         else if(i==j)dp[i][j]=(dp[i][j-1]+1)%mod;
22         else 
23         dp[i][j]=dp[i][j-1];
24     }
25 }
26 int main()
27 {
28     int n,m;
29     solve();
30     while(~scanf("%d%d",&n,&m))
31     {
32         printf("%d
",dp[n][m]);
33     }
34     return 0;
35 }

View Code