ICPC 2018 焦作网络预赛 K. Transport Ship

【题目链接】

题目意思

T组案例，第一行T，第二行两个数字N，M，表示有N种船只，M次询问，接下来N行，每行两个数字v[i],c[i]，每种船只的载货量为v[i]，每种船只有2^c[i]-1种，有M次询问，每次询问给出一个数字s，问有多少种载货方式填满容量s。

样例输入
1
1 2
2 1
1
2
样例输出
0
1

解题思路

针对与每种船有2 ^ c[i]-1，可以想到任何一个数字都可以由2 ^ 0+2 ^ 1+2 ^ 2+…+2 ^ (c[i]-1)中的任意项组成，因此，可以将1，2，4，8，16 ，2^(c[i]-1)个船看成一种船，然后进行01背包判断有多少种装满的方案。

AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
ll dp[10005];
int val[10005], cnt[10005];
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		memset(dp, 0, sizeof dp);
		dp[0] = 1;
		int n, m, q;
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; i++)
		{
			scanf("%d%d", &val[i], &cnt[i]);
			for (int j = 0; j < cnt[i]; j++)
			{
				ll temp = val[i] * (1 << j);
				for (int k = 10004; k >= temp; k--)
					dp[k] = (dp[k] + dp[k - temp]) % mod;
			}
		}
		for (int i = 0; i < m; i++)
		{
			scanf("%d", &q);
			printf("%lld\n", dp[q]);
		}
	}
}