poj 3046 Ant Counting——多重集合的背包

多重集合的背包问题。

1.式子：考虑dp[ i ][ j ]能从dp[ i-1 ][ k ]（max(0 , j - c[ i ] ) <= k <= j）转移来。

　　对于j<=c[ i ]，这就是前缀和一样，所以dp[ i ][ j ] = dp[ i ][ j-1 ] + dp[ i-1 ][ j ]；

　　对于j>c[ i ]，加了dp[ i ][ j-1 ] + dp[ i-1 ][ j ]之后会多加了一项dp[ i-1 ][ j-c[ i ]-1 ]，减掉即可。

2.意义：dp[ i-1 ][ j ]表示从前面组中选 j 个，dp[ i ][ j-1 ]表示从本组+前面组中选了 j-1 个，再在本组中选1个。

　　有一个不合法的情况是dp[ i ][ j-1 ]中已经选了c[ i ]个本组的，就不能再在本组中选1个了。

　　而 dp[ i ][ j-1 ]中已经选了c[ i ]个本组的的方案数就是前面组中选了 j-1-c[ i ] 个的方案数（这样选 j-1 的时候就必须选c[ i ]个本组的了）。减掉即可。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=,M=1e5+,mod=1e6;

int n,m,c[N],l,r,dp[][M],ans;

int main()

{

    scanf("%d%d%d%d",&n,&m,&l,&r);int x;

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

    {

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

    }

    dp[][]=dp[][]=;

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

    {

        int u=(i&),v=!u;

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

        {

            dp[u][j]=(dp[v][j]+dp[u][j-])%mod;

            if(j>c[i])dp[u][j]=((dp[u][j]-dp[v][j-c[i]-])%mod+mod)%mod;

        }

    }

    int u=(n&);

    for(int j=l;j<=r;j++)(ans+=dp[u][j])%=mod;

    printf("%d",ans);

    return ;

}

巴特西

poj 3046 Ant Counting——多重集合的背包

最新文章

热门文章