Ant Counting POJ - 3046 (多重集组合数&dp优化)
多重集组合数:
有n种物品,第i种物品有ai个。不同种类的物品可以互相区分但相同种类的无法区分。从这些物品中取出m个的话,有多少种取法?求出方案数模M的余数
为了不重复计数,同一种种类的物品最好一次处理,定义:
dp[i+1][j]:=从前i种物品种取出j个的组合总数
为了从前i种物品种取出j个,可以从前i-1种物品中取出j-k个,再从第i种物品中取出k个添加进来,得到递推式:
直接计算这个递推关系的话复杂度时O(NM^2),不过可以看下如下优化:
int n,m;
int a[MAXN];
int dp[MAXN+1][MAXM+1];
void solve()
{
for(int i=0;i<=n;i++){
dp[i][0]=1;
}
for(int i=0;i<n;i++){
for(int j=1;j<=m;j++){
if(j-1-a[i]>=0){
dp[i+1][j]=(dp[i+1][j-1]+dp[i][j]-dp[i][j-1-a[i]]+M)%M;
}else{
dp[i+1][j]=(dp[i+1][j-1]+dp[i][j])%M;
}
}
}
printf("%d\n",dp[n][m]);
}
附上代码(可以看出,这个实际上可以用个二维数组进行滚动优化):
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXT=1010;
const int MOD=1000000;
int a[MAXT];
int dp[2][MAXT*100];
int main()
{
int t,n,s,b;
while(scanf("%d%d%d%d",&t,&n,&s,&b)!=EOF){
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
int x;
for(int i=0;i<n;i++){
scanf("%d",&x);
a[x-1]++;
}
dp[0][0]=dp[1][0]=1;
for(int i=0;i<t;i++){
for(int j=1;j<=b;j++){
if(j-1-a[i]>=0){
dp[(i+1)&1][j]=(dp[(i+1)&1][j-1]+dp[i&1][j]-dp[i&1][j-1-a[i]]+MOD)%MOD;
}else{
dp[(i+1)&1][j]=(dp[(i+1)&1][j-1]+dp[i&1][j])%MOD;
}
}
}
int ans=0;
for(int i=s;i<=b;i++){
ans=(ans+dp[t&1][i])%MOD;
}
printf("%d\n",ans);
}
return 0;
}