ACM-ICPC 2018 焦作赛区网络预赛 K Transport Ship(多重背包)

本文主要是介绍ACM-ICPC 2018 焦作赛区网络预赛 K Transport Ship(多重背包)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://nanti.jisuanke.com/t/31720

 

题目大意：n个船，每个船载重vi，数量2^ci-1，问载重正好是s有几种情况

 

题目思路：由于固定了数量，所以很容易想到是多重背包。问的是方案数，所以设dp[0]为1，剩下来初始化为0，然后上去跑多重背包板子就过了

 

以下是代码：

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long 
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const int MOD = 1e9+7;
const int MAXN = 1e4+5;
struct node{int v,c;
}a[30];
ll dp[MAXN];
int main(){int n,q,s;int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&q);rep(i,1,n)scanf("%d%d",&a[i].v,&a[i].c),a[i].c=(1<<a[i].c)-1;memset(dp,0,sizeof(dp));dp[0]=1;rep(i,1,n){if(a[i].c*a[i].v>=MAXN){rep(j,a[i].v,MAXN){dp[j]=(dp[j]+dp[j-a[i].v])%MOD;}}else{int k=1,temp=a[i].c;while(k<temp){per(j,MAXN,k*a[i].v){dp[j]=(dp[j]+dp[j-k*a[i].v])%MOD;}temp-=k;k<<=1;}per(j,MAXN,temp*a[i].v){dp[j]=(dp[j]+dp[j-temp*a[i].v])%MOD;}}}rep(i,1,q){scanf("%d",&s);printf("%lld\n",dp[s]);}}return 0;
}

 

这篇关于ACM-ICPC 2018 焦作赛区网络预赛 K Transport Ship(多重背包)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---