题目: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;
}