poj3046 Ant Counting——多重集组合数

题目：http://poj.org/problem?id=3046

就是多重集组合数（分组背包优化）；

从式子角度考虑：(干脆看这篇博客) https://blog.csdn.net/viphong/article/details/48110525

从意义的角度来考虑：

当 j<=a[i] 时，f[i][j] = f[i-1][j]  + f[i][j-1]，就是分成了不选第 i 种物品和至少选一个第 i 种物品的情况，其中 f[i][j-1] 代表 j-1 后剩下的那一个物品一定是第 i 种；

当 j>a[i] 时，f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1-a[i]]，因为此时 j-1 后第 i 种物品可能仍然已经被选满( j - 1 >= a[i] )，无法再至少来一个 i 物品，所以减去 j-1 后 i 被选满的情况。

 代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const maxn=1e5+5,mod=1e6;
int n,m,st,ed,f[3][maxn],a[1005],ans;
int main()
{
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    for(int i=1,x;i<=m;i++)
        scanf("%d",&x),a[x]++;
    f[0][0]=1;f[1][0]=1; 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=ed;j++)
        {
            if(j<=a[i])f[i%2][j]=(f[i%2][j-1]+f[(i+1)%2][j])%mod;
            else f[i%2][j]=(f[i%2][j-1]+f[(i+1)%2][j]-f[(i+1)%2][j-1-a[i]]+mod)%mod;//+mod
        }    
    for(int j=st;j<=ed;j++)
        (ans+=f[n%2][j])%=mod;
    printf("%d
",ans);
    return 0;
}