hdu 2809(状压dp)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2809

思路:简单的状压dp,看代码会更明白。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; struct State{
int ati,def,hp,lev,exp;
}dp[<<+]; struct Node{
int ati,def,hp,exp;
}node[]; int n;
int In_ati,In_def,In_hp;
char str[]; int main()
{
while(~scanf("%d%d%d%d%d%d",&dp[].ati,&dp[].def,&dp[].hp,&In_ati,&In_def,&In_hp)){
scanf("%d",&n);
for(int i=;i<n;i++){
scanf("%s%d%d%d%d",str,&node[i].ati,&node[i].def,&node[i].hp,&node[i].exp);
}
for(int i=;i<(<<)+;i++){
dp[i].hp=;
}
dp[].lev=;
dp[].exp=;
for(int state=;state<(<<n);state++){
if(dp[state].hp<=)continue;
for(int i=;i<n;i++){
if(state&(<<i))continue;
State S=dp[state];
int tmp1=max(,S.ati-node[i].def);
int tmp2=max(,node[i].ati-S.def);
int t=(node[i].hp/tmp1)+((node[i].hp%tmp1==)?-:);
S.hp-=t*tmp2;
if(S.hp<=)continue;
S.exp+=node[i].exp;
if(S.exp>=S.lev*){
S.lev++;
S.ati+=In_ati;
S.def+=In_def;
S.hp+=In_hp;
}
if(S.hp>dp[state|(<<i)].hp){
dp[state|(<<i)]=S;
}
}
}
if(dp[(<<n)-].hp<=){
puts("Poor LvBu,his period was gone.");
}else
printf("%d\n",dp[(<<n)-].hp);
}
return ;
}
上一篇:解决ie低版本不认识html5标签


下一篇:JS字符串方法总结整理