http://acm.hdu.edu.cn/showproblem.php?pid=2809
HH大牛出的題目，比賽的時(shí)候被唬住了沒(méi)有去做，今天興致來(lái)了認(rèn)真敲了一下，秒殺
這題跟1074doing homework一樣，位壓縮，沒(méi)的說(shuō)，自底向上計(jì)算，見(jiàn)圖
#include<iostream>
using namespace std;
#define N 1100000
int m,n,hp,ati,def;
struct node
{
int ati;
int def;
int hp;
int lv;
int exp;
}q[N],tt;
struct man{
int ati;
int def;
int hp;
int exp;
}man[21];
int max(int a,int b)
{
return a>b?a:b;
}
int war(int j,int i)
{
int time;
time=man[i].hp/max(1,q[j].ati-man[i].def);
if(man[i].hp%max(1,q[j].ati-man[i].def)==0)
time--;
if(time>=0)
return time;
return -1;
}
void dp()
{
int i,j,time,add,temp,next;
for(j=0;j<m;j++)
{
if(q[j].hp<=0)
continue;
for(i=0;i<n;i++)
{
temp=j>>i;
if(temp&1)
continue;
else
next=j+(1<<i);
if((time=war(j,i))==-1)
continue;//戰(zhàn)斗失敗，continue
tt=q[j];
tt.hp-=time*max(1,man[i].ati-tt.def);
tt.exp+=man[i].exp;
if(tt.exp>=100)
{
add=tt.exp/100;
tt.exp%=100;
tt.ati+=add*ati;
tt.def+=add*def;
tt.hp+=add*hp;
tt.lv+=add;
}
if(q[next].hp==0||tt.hp>q[next].hp||(q[next].hp==tt.hp&&(tt.lv*100+tt.exp)>(q[next].lv*100+q[next].exp)))
{
q[next]=tt;
}
}
q[j].hp=0;
}
}
int main()
{
int i;
char name[22];
while(scanf("%d%d%d%d%d%d",&q[0].ati,&q[0].def,&q[0].hp,&ati,&def,&hp)>0)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%s%d%d%d%d",name,&man[i].ati,&man[i].def,&man[i].hp,&man[i].exp);
m=(1<<n)-1;
q[0].lv=1;
q[0].exp=0;
for(i=1;i<=m;i++)
{
q[i].hp=0;
}
dp();
if(q[m].hp>0)
printf("%d\n",q[m].hp);
else
printf("Poor LvBu,his period was gone.\n");
}
return 0;
}
posted on 2009-11-26 20:46
西風(fēng)蕭瑟 閱讀(1475)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
動(dòng)態(tài)規(guī)劃