【计蒜客】2018ICPC焦作赛区网络赛K Transport Ship（多重背包+dp）

题目链接

 

【题意】

给定N种船，每种船有2^C[i]-1艘，每种船能承载V[i]的货物，有q个询问，问选择若干艘船装满重量为S的方案总数。

【解题思路】

嗯……很明显的题意，比赛的时候居然这题看都没看？！！

只要利用二进制转换成01背包即可。dp[j]表示用若干艘船装成重量为j的方案数。所以动态转移方程为dp[j]=dp[j-w[i]]+dp[j]。

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e4+5;
const int mod=1e9+7;
LL dp[maxn],c[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    for(int i=0;i<21;++i)c[i]=(1<<i)-1;
    while(T--)
    {
        int n,q,wi,t;
        vector<int>w;
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        scanf("%d%d",&n,&q);
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&wi,&t);
            t=c[t];
            for(int j=1;j<=t;j<<=1)
            {
                w.push_back(j*wi);
                t=t-j;
            }
            if(t>0)
                w.push_back(t*wi);
        }
        for(int i=0;i<w.size();i++)
            for(int j=10000;j>=w[i];j--)
                dp[j]=(dp[j]+dp[j-w[i]])%mod;
        while(q--)
        {
            int x;
            scanf("%d",&x);
            printf("%lld\n",dp[x]%mod);
        }
    }
    return 0;
}