【CCF Online3普及组】买表

(File IO): input:watch.in output:watch.out

题目描述

Jimmy 到 Symbol 的手表店买手表，Jimmy 只带了 n 种钱币，第 i种钱币的面额为 k_i元，张数为 a_i张。Symbol 的店里一共有 m块手表，第 i块手表的价格为 t_i 元。
Symbol 的手表店不能找零，所以 Jimmy 只能在凑出恰好的钱数时才能购买一块手表。现在对于店里的每块手表，Jimmy 想知道他能不能凑出恰好的钱数进行购买。

输入

第一行两个空格分隔的整数 n和 m表示钱币数与手表数。

接下来 n行每行两个空格分隔的整数 k_i，a_i表示钱币的面额和张数。

第 n+2行，共 m个用空格分隔的整数 t_i，表示每块手表的价格。

输出

一共 m行，对于第 i行，如果能凑出恰好的钱数购买第 i块手表则输出"Yes"（不含引号，下同），否则输出"No"，注意只有首字母大写。

样例输入

3 5
1 2
5 1
6 3
3 19 21 1 7

样例输出

No
Yes
No
Yes
Yes

数据范围限制

对于 50%的数据，n≤10，m≤60，a_i≤20，k_i≤5000，t_i​≤250。

对于 100%的数据，1≤n≤200，1≤m≤10^5，1≤a_i​≤1000，1≤k_i​≤500000，0≤t_i≤500000。

提示

第二块手表 19=6×3+1=6×2+5+1×2，可以恰好凑出。

第四块手表 1=1×1，可以恰好凑出。

第五块手表 7=5+2×1=6×1+1，可以恰好凑出。

想当年，我五年级时，参加这个比赛，写了个暴搜，骗了个40分。这道题显然是一个动态规划的背包问题，但是如果写多重背包的话，那就只能拿50分，而这道题的正确写法应该是01背包+二进制优化。把面额同时当作重量和价值，再把多重背包转化成01背包，再加上二进制优化，再写一段动规，输出，就可以了。把多重背包转化成01背包大家应该都会，假如第一、二、三个数分别是重量、价值、数量，那么，例如：
3 4 4
可以转为
3 4 1
3 4 1
3 4 1
3 4 1
再把后面的1去掉，就变成01背包了。但这样还远远不够，我们还需要二进制优化。但是应该怎么优化呢？例如：
3 4 4
可以转为
3×1 4×1
3×2 4×2
3×1 4×1
即
3 4
6 8
3 4

再例如：
3 4 17
可以转为
3×1 4×1
3×2 4×2
3×4 4×4
3×8 4×8
3×2 4×2
即
3 4
6 8
12 16
24 32
6 8

为什么可以这样转呢？大家从中可以发现，经过拆分，我们依然可以组成数量为1 ~ 4（或14，在例子中）的情况，且不遗漏，也不会多算。是不是很神奇？观察第二个乘数，除了第一和最后一组，每一组都是前一组的两倍。大家知道，2⁰+2¹+2²+……+2ⁿ=2ⁿ⁺¹-1，二进制优化就是根据这一个原理来做到不遗漏的（且让组数尽量小，来提高程序效率）。但是最后一组又是怎么回事？咱们来看看第二个例子。如果把第二个例子的最后一组删掉，我们就只能组成数量为1 ~ 15的情况。这时，还时还差2，才能组成数量为1~17的情况，这时，我们只需要加上一组3×2 4×2，就可以解决了。

#include<cstdio>
int nn,n,m,k[205],a[205],maxx,t[100005],kk[200005],dp[500005];
int max(int x,int y)
{
	return x>y?x:y;
}
int main()
{
	freopen("watch.in","r",stdin);
	freopen("watch.out","w",stdout);
	scanf("%d%d",&nn,&m);
	for(int i=1;i<=nn;++i)
	{
		scanf("%d%d",&k[i],&a[i]);
	}
	for(int i=1;i<=m;++i)
	{
		scanf("%d",&t[i]);
		if(t[i]>maxx)//求m个手表的最大价格
		{
			maxx=t[i];
		}
	}
	for(int i=1;i<=nn;++i)
	{
		int p=1;//二进制优化，p就是第二个乘数
		while(a[i]>=p)//判断是否还能拆分
		{
			if(p*k[i]>maxx) break;//如果面额大于手表的最大价值，那这张纸币就没用了
			n++;
			kk[n]=p*k[i];//把经过处理的数放到新的数组里，kk即表示“重量”，也表示“价值”（题目中不是重量和价值）
			a[i]-=p;//减上p，做到不多算
			p*=2;
		}
		if(a[i]>0&&a[i]*k[i]<=maxx)//处理最后一组
		{
			n++;
			kk[n]=a[i]*k[i];
		}
	}
	for(int i=1;i<=n;++i)//动规
	{
		for(int j=maxx;j>=kk[i];--j)
		{
			dp[j]=max(dp[j],dp[j-kk[i]]+kk[i]);
		}
	}
	for(int i=1;i<=m;++i)
	{
		if(dp[t[i]]==t[i])//如果可以组成
		{
			printf("Yes\n");
		}
		else
		{
			printf("No\n");
		}
	}
}

不见不散（新年好！！！）