动态规划：多重集组合数

有n种物品, 第i种物品有a个. 不同种类的物品可以互相区分, 但相同种类的无法区分

从这些物品中取出m个, 有多少种取法

求多重集组合数，并没有让枚举多重集组合

可是枚举应该怎么枚举呢？哈希判重？

dp[i][j] 表示前i种物品,一共拿了j个物品的方法数

为了得到dp[i][j]，那么可以从前i-1种物品取j-k个,再从第i种物品取k个即可

这个公式是O（n（m^2））的

优化一下效率

决策：第i种不选或者至少选一个

dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-ant[i]-1]

然后给出实现，这里的答案把m的值从S到B都累加了

 1 #include<cstdio>
 2 using namespace std;
 3 const int maxn=100005;
 4 const int MOD=1000000;
 5 int T,A,S,B,ans;
 6 int a[1005];  //一共这么多种，存每种几个 
 7 int f[2][maxn];
 8 int main()
 9 {
10     int x;
11     scanf("%d%d%d%d",&T,&A,&S,&B);
12     for(int i=1;i<=A;i++)
13     {
14         scanf("%d",&x);
15         a[x]++;
16     } 
17     f[0][0]=f[1][0]=1;
18     for(int i=1;i<=T;i++)  //一共几种数
19     for(int j=1;j<=B;j++)  //Cn取m的那个m
20         if(j-a[i]-1>=0)
21             f[i%2][j]=(f[(i-1)%2][j]+f[i%2][j-1]-f[(i-1)%2][j-a[i]-1]+MOD)%MOD;
22         else f[i%2][j]=(f[(i-1)%2][j]+f[i%2][j-1])%MOD;
23     for(int i=S;i<=B;i++)
24         ans=(ans+f[T%2][i])%MOD;
25     printf("%d",ans);
26     return 0;
27 }

其实这个题给我印象最深的地方是%2，让我立刻想起了NOIP2014day1T3激扬的小鸟的满分做法