Posted on 2010-08-05 22:37
Onway 閱讀(869)
評論(2) 編輯 收藏 引用 所屬分類:
傷不起的ACM
HDU 2159 FATE 二維費用的背包
在pku用二維費用重做了一次1882以后，發現這個題其實也挺簡單的。
先說一下pku1882，第一個費用是張數，第二個費用是與價值等同的重量，即題中的面值。
可以設計狀態為f[i][j]表示用到第i張郵票組成面值為j時能獲得的最大價值，即能組成最大的面值（<=j）。然后是轉化為完全背包來做，循環順序由低到高。
然后hdu 2159比pku 1882好處理，要處理的數據比較少。不同的是，二維費用改變了，背包狀態的設計也改變了。
設f[i][j]表示殺到第i個怪，忍耐度在j的時候能獲得的最大價值。注意這樣設計狀態的話，開的數組不用很大。我是數組開小了，貢獻了一次RE，很厚道，報的是RE，如果是WA，就難受了。
這樣設計狀態，在后面查找結果的時候要對j進行一次歷遍查找。
#include <iostream>
using namespace std;
int data[101][2],exp[101][101];
int fmax(int a,int b)
{return a>b?a:b;}
int main()
{
int rem,bear,kind,kill;
while(scanf("%d%d%d%d",&rem,&bear,&kind,&kill)!=EOF)
{
int i,j,k;
for(i=1;i<=kind;++i)
scanf("%d%d",&data[i][0],&data[i][1]);
memset(exp,0,sizeof(exp));
for(i=1;i<=kind;++i)
for(j=1;j<=kill;++j)
for(k=data[i][1];k<=bear;++k)
exp[j][k]=fmax(exp[j][k],exp[j-1][k-data[i][1]]+data[i][0]);
for(i=kill,j=1;j<=bear;++j)
if(exp[i][j]>=rem)
break;
if(j>bear)
printf("%d\n",-1);
else
printf("%d\n",bear-j);
}
return 0;
}