搜索
您的当前位置:首页正文

poj 3046 dp(有重复元素的组合数)

来源:欧得旅游网

题意:给出T种数字(1~T)。每种各有N[i]个。然后用这些数字构成的元素数量在a~b之间的组合数之和。

例如全集={1, 1, 2, 2, 3},即数字1和2出现两次,数字3出现1次。
那么元素数量为1的组合有3种: {1} {2} {3}
元素数量为2的组合有5种: {1,1} {1,2} {1,3} {2,2} {2,3}
元素数量为3的组合有5种: {1,1,2} {1,1,3} {1,2,2} {1,2,3} {2,2,3}
元素数量为4的组合有3种: {1,2,2,3} {1,1,2,2} {1,1,2,3}
元素数量为5的组合有1种: {1,1,2,2,3}

思路:动态规划。dp[i][j]表示用1~i这些数字,元素数量为j的个数。那么对每个dp[i][j],枚举数字i出现的次数即可求。复杂度为T*N(每种数字出现的最多次数,为100)*A(元素数量的上界)。这个地方可以优化到T*A,维护一个部分和即可。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define INF 0x3fffffff
#define clr(s,t) memset(s,t,sizeof(s))
#define N 100005
int dp[2][N],s[1005];
int n,m,be,en;
int main(){
    int i,j,now,a,b,res=0;
    scanf("%d %d %d %d",&n,&m,&be,&en);
    memset(s,0,(n+1)*sizeof(int));
    for(i = 0;i<m;i++){
        scanf("%d",&j);
        s[j]++;
    }
    dp[0][0] = 1;
    a = 1;
    b = 0;
    for(i = 1;i<=n;i++){
        a = 1-a;
        b = 1-b;
        dp[b][0] = now = 1;//now是部分和
        for(j = 1;j<=en;j++){
            if(j<=s[i])
                now += dp[a][j];
            else
                now += dp[a][j]-dp[a][j-s[i]-1]+1000000;
            now %= 1000000;
            dp[b][j] = now;
        }
    }
    for(j = be;j<=en;j++){
        res += dp[b][j];
        res %= 1000000;
    }
    printf("%d\n",res);
}


因篇幅问题不能全部显示,请点此查看更多更全内容

热门图文

Top