Posted on 2010-08-05 22:37
Onway 阅读(842)
评论(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;
}