1143: 三国风云
时间限制: 2 Sec 内存限制: 128 MB
题目描述
在公元前184~280年，在华夏大地上建立起了许多国家，其中最强的三个就是，魏国、蜀国、吴国。人们称这一时期为“三国”。
小明是一个超级三国迷，他喜欢三国中的英雄及其故事。在众多英雄中，他最喜欢的就是战神吕布。
吕布是三国中最具有战斗天赋的一个，有“God of War”之称，虽然他的战斗力十分强大，但是他的野心太大。许多诸侯都想把他杀死。在公元前198年，曹操发现吕布正在徐州城。虽然吕布被成为战争之神，但是曹操拥有众多武将：许褚、典韦、夏侯淳等等。面对如此众多的英雄，吕布能战胜他们获得胜利么？
给出吕布的ATI，DEF，HP，以及对手的ATI，DEF，HP，和experience(如果吕布将对手杀死，他将得到这个数值的经验，如果他总经验到达等级数*100，他将升级，并且变得更加强大)。
每一个回合，吕布将选择一个对手，与自己决斗。请你帮助吕布找到一个战胜所有对手的策略，并使得所有战斗结束之后的HP值最大。
下面是一场吕布和A之间的战斗：
如果吕布攻击A，A将会受到Max（1，吕布的ATI-A的DEF）的伤害，并且hp减去该伤害；
如果A在上一轮攻击中幸存下来了，他将反击，并对吕布造成Max（1，A的ATI-吕布的DEF）的伤害
如果吕布仍然存活，那他将继续攻击，直到有一方死亡(hp<=0).
输入
第一行包含六个数。分别为吕布的ATI，DEF，HP以及In_ATI,In_DEF,In_HP。
然后给出一个整数N(0 < N <= 20),表示敌人的数目。
下面有N行，每行开始，一个字符串，name(不超过20个字符，表示武将名字),以及改名武将的ATI，DEF,HP,experience(1 < experience <= 100).
输出
如果吕布挂了，输出”Poor LvBu,his period was gone.”
否则输出吕布能省下最大的HP。
样例输入
100 80 100 5 5 5
2
ZhangFei 95 75 100 100
XuChu 90 90 100 90
样例输出
30
提示
100 75 100 5 5 5 1
GuanYu 95 85 100 100
Poor LvBu,his period was gone.
题解：
同学们题目要读清楚啊。
应该是一道很水的状压dp吧，枚举一下状态，然后模拟。
Code:
using namespace std;
int atii[
25],defi[
25],hpi[
25],expi[
25];
int ati[N],def[N],hp[N],expn[N],in_ati,in_def,in_hp,n;
char ch[
25];
int main()
{
scanf(
"%d%d%d%d%d%d",&ati[
0],&def[
0],&hp[
0],&in_ati,&in_def,&in_hp);
scanf(
"%d",&n);
for(
int i=
1;i<=n;i++)
scanf(
"%s%d%d%d%d",ch,&atii[i],&defi[i],&hpi[i],&expi[i]);
for(
int i=
0;i<(
1<<n)-
1;i++)
{
if(hp[i]==
0)
continue;
for(
int j=
1;j<=n;j++)
if((i&(
1<<j-
1))==
0)
{
int x=((hpi[j]-
1)/max(
1,ati[i]-defi[j]))
*max(
1,atii[j]-def[i]);
if(
x>=hp[i])
continue;
int y=(expn[i]+expi[j])/
100;
expn[xp]=(expn[i]+expi[j])
0;
ati[xp]=ati[i]+
y*in_ati;
def[xp]=def[i]+
y*in_def;
hp[xp]=max(hp[xp],hp[i]+
y*in_hp-
x);
}
}
if(hp[(
1<<n)-
1])
printf(
"%d\n",hp[(
1<<n)-
1]);
else
puts(
"Poor LvBu,his period was gone.");
return 0;
}
