ACM-ICPC 2018 焦作赛区网络预赛 K. Transport Ship (多重背包+方案记录)
程序员文章站
2022-06-04 12:08:00
...
K. Transport Ship
样例输入
1
1 2
2 1
1
2
样例输出
0
1
查询的时候注意下技巧就可以过啦~
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int mod=1e9+7;
const int MAXN = 25;
int pri[MAXN], wei[MAXN];
long long num[MAXN];
int dp[10010], sum, n;
long long number[10010];
void zeroOnePack(int price, int weight, int sum)
{
for (int i = sum; i >= price; i--)
{
dp[i] = max(dp[i], dp[i - price] + weight);
if(dp[i]==dp[i-price]+weight)
number[i]=(number[i]+number[i-price])%mod;
}
}
void completePack(int price, int weight, int sum)
{
for (int i = price; i <= sum; i++)
{
dp[i] = max(dp[i], dp[i - price] + weight);
if(dp[i]==dp[i-price]+weight)
number[i]=(number[i]+number[i-price])%mod;
}
}
void multiPack(int n, int sum)
{
memset(dp, 0, sizeof(dp));
memset(number,0,sizeof(number));number[0]=1;
for (int i = 1; i <= n; i++)
{
if (pri[i] * num[i] > sum)
completePack(pri[i], wei[i], sum);
else
{
for (long long k = 1; k < num[i]; k *= 2)
{
zeroOnePack(k * pri[i], k * wei[i], sum);
num[i] -= k;
}
if (num[i] != 0)
zeroOnePack(num[i] * pri[i], num[i] * wei[i], sum);
}
}
}
void solve()
{
int q;
scanf("%d%d",&n,&q);
int v,c;
for (int i = 1; i <= n; i++)
{
scanf("%d%d",&v,&c);
pri[i]=wei[i]=v;
num[i]=pow(2,c)-1;
}
sum=10000;
multiPack(n,sum);
int qt;
for(int i=0; i<q; i++)
{
scanf("%d",&qt);
printf("%lld\n",number[qt]%mod);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
solve();
return 0;
}