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

ACM-ICPC 2018 焦作赛区网络预赛 K. Transport Ship (多重背包+方案记录)

程序员文章站 2022-06-04 12:08:00
...

K. Transport Ship

传送门

ACM-ICPC 2018 焦作赛区网络预赛 K. Transport Ship (多重背包+方案记录)
ACM-ICPC 2018 焦作赛区网络预赛 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;
}