欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-04 12:07:54
...

题目链接

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

【计蒜客】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;
}