【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，在例子中）的情況，且不遺漏，也不會多算，是不是很神奇？觀察第二個乘數，除了第一和最后一組，每一組都是前一組的兩倍，大家知道，20+21+22+……+2n=2n+1-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");
}
}
}
不見不散（新年好！！！）
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/259274.html
標籤：其他
上一篇：字體檔案格式詳解