poj3046 Ant Counting——多重集组合数

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

从式子角度考虑：(干脆看这篇博客) 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+,mod=1e6;

int n,m,st,ed,f[][maxn],a[],ans;

int main()

{

    scanf("%d%d%d%d",&n,&m,&st,&ed);

    for(int i=,x;i<=m;i++)

        scanf("%d",&x),a[x]++;

    f[][]=;f[][]=;

    for(int i=;i<=n;i++)

        for(int j=;j<=ed;j++)

        {

            if(j<=a[i])f[i%][j]=(f[i%][j-]+f[(i+)%][j])%mod;

            else f[i%][j]=(f[i%][j-]+f[(i+)%][j]-f[(i+)%][j--a[i]]+mod)%mod;//+mod

        }

    for(int j=st;j<=ed;j++)

        (ans+=f[n%][j])%=mod;

    printf("%d\n",ans);

    return ;

}

巴特西

poj3046 Ant Counting——多重集组合数

最新文章

热门文章