poj 3046 Ant Counting (DP多重双肩包变形)

poj 3046 Ant Counting (DP多重背包变形)

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

思路： dp [i] [j] :=前i种 构成个数为j的方法数。

#include <cstdio>
#include <cstring>
#include <iostream>
int T,A,S,B;
int hash[1010];
int dp[1010][10100];

const int MOD=1e6;
using namespace std;
int main(){

    while(cin>>T>>A>>S>>B){
        memset(hash,0,sizeof(hash));
        for(int i = 1; i <= A; i++){
            int u;
            cin>>u;
            hash[u]++;
        }
        memset(dp,0,sizeof(dp));
        for(int i = 0; i <= hash[1]; i++) dp[1][i] = 1;//第一种取1~k
        for(int i = 2; i <= T; i++)
            for(int j = 0; j <= B; j ++){
                for(int k = 0; k <= hash[i]; k++)
                    if(j >= k) {
                        dp[i][j] += dp[i-1][j-k];
                        dp[i][j] %= MOD;
                    }else break;
            }
        int sum = 0;
        for(int i = S; i <= B; i++){
            sum+= dp[T][i];
            sum %= MOD;
        }
       cout<<sum<<endl;
    }
    return 0;
}