HDU 2809 God of War(DP + 状态压缩)

时间:2022-11-21 00:38:13

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

题目大意:给出战神吕布的初始攻击力ATI、防御力DEF、生命值HP、每升一级增加的攻击力In_ATI,增加的防御力In_DEF和增加的生命值In_HP。然后给出n个敌人的攻击力、防御力、生命值和杀死该单位能获得的经验值EXP。  吕布的初始经验值EXP是0,初始等级level是1,每当EXP>=level*100时就会升级。

  在吕布LvBu和敌人A之间的战斗有3条规则

  1.吕布攻击A,A失去 Max(1,LvBu's ATI- A's DEF) HP;

  2.A攻击吕布,吕布失去Max(1,A'ATI- LvBu'DEF)HP;

  3.战斗持续到任意一方死亡

如果吕布能够将全部敌人杀死,并且自己不死,那么输出能够余下的最大HP,否则输出"Poor LvBu,his period was gone."

Sample Input
100 80 100 5 5 5
2
ZhangFei 95 75 100 100
XuChu 90 90 100 90
100 75 100 5 5 5
1
GuanYu 95 85 100 100
 
Sample Output
30
Poor LvBu,his period was gone.

分析:

由于涉及到最优结果 以及 单挑顺序对结果带来的影响,使用状态压缩dp来解这道题。

想讲一下思路,比如现在吕布跟三个人战斗,用1表示已经战胜这个人, 0表示没有。那个所有的情况(在不考虑顺序的情况下)就有2的3次方,8种可能,包括000。用对应的十进制表示。如图

HDU 2809 God of War(DP + 状态压缩)

  可见,3的状态可以由1,2来求,5可以用1,4来求,6可以用2, 4来求,7可以用3, 5, 6状态来求,这就有了一个状态转移的方程在里面了。

有些同学就想问那顺序怎么办呢。

  我们要计算3的最优状态的时候,会由1,跟2,来推出

  1状态表示打败第一个人

  2状态只表示第二个人

  那么3状态由1状态来计算的时候,就是先打第一个人再打第二个人

  而3状态由2状态来计算的时候,就是先打第二个人再打第一个人, 计算后的结果与当前的3状态的结果比较,把最优的覆盖上去就可以了。

  这个过程是不是有了一个顺序在里面了呢。

  而在代码里面,我们是由底向上计算额。比如历遍到第1个状态点的。我们可以计算上面的第3个点,跟第5个状态点,寻找的过程由位运算来实现。

代码如下:

 # include<stdio.h>
# include<string.h>
int max(int a,int b){
return a>b ?a :b;
}
struct Lvbu{
int ATI,DEF,HP,EXP,level;
}lv,dp[<<]; //dp[i]表示在在集合i下,吕布能达到的最好状态 struct Enemy{
char name[];
int ATI,DEF,HP,EXP;
}en[]; int In_ATI,In_DEF,In_HP,n; int main(){
int i,j;
while(scanf("%d%d%d%d%d%d",&lv.ATI,&lv.DEF,&lv.HP,&In_ATI,&In_DEF,&In_HP) != EOF){
lv.EXP = ; //吕布初始经验为0,初始等级为1
lv.level = ;
scanf("%d",&n);
for(i=;i<n;i++)
scanf("%s%d%d%d%d",en[i].name,&en[i].ATI,&en[i].DEF,&en[i].HP,&en[i].EXP);
int s,recent;
int endstate = <<n;
dp[] = lv; //dp[0]表示集合0,即没有攻击任何一个敌人时,吕布的状态,初始化
bool flag; for(s=; s<endstate; s++){
flag = false; //判断是否可以打败敌人
for(i=; i<n; i++){
recent = <<i;
if(s & recent){ //如果在该集合里边,吕布打败了第i个敌人
Lvbu tmp=dp[s^recent]; //取出吕布没有打败第i个人,但是打败了状态s里边的其他所有人
if(tmp.level < ) continue; //已经死亡
int dec = tmp.ATI - en[i].DEF; //吕布的攻击力
if(dec <= ) dec = ; //特殊情况 int times = en[i].HP / dec; //吕布杀死敌人的时间
if(times * dec != en[i].HP) times++; dec = en[i].ATI - tmp.DEF; //敌人的攻击力
if(dec <= ) dec = ;
tmp.HP -= dec*(times - ); //吕布受到的伤害 if(tmp.HP <= ) continue; //如果死亡,跳出 tmp.EXP += en[i].EXP; //获得该角色经验
if(tmp.EXP >= tmp.level* ){ //如果经验足够升级
int add = tmp.EXP/ - tmp.level + ; //可升多少级
tmp.level += add; //各项技能强化
tmp.ATI += add*In_ATI;
tmp.DEF += add*In_DEF;
tmp.HP += add*In_HP;
}
if(!flag || (tmp.HP>dp[s].HP) ||tmp.level>dp[s].level){ //选取最优的方案,并且置flag为真
dp[s] = tmp;
flag = true;
}
}
}
if(!flag) dp[s].level = -; //如果不能打败该集合里的敌人,那么令等级为-1
} lv = dp[endstate -]; //将所有敌人打倒的状态 (1<<n)-1
if(lv.level < )
printf("Poor LvBu,his period was gone.\n");
else
printf("%d\n",lv.HP);
}
return ;
}

HDU 2809 God of War(DP + 状态压缩)的更多相关文章

  1. HDU 1074 Doing Homework (dp&plus;状态压缩)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1074 题目大意:学生要完成各科作业, 给出各科老师给出交作业的期限和学生完成该科所需时间, 如果逾期一 ...

  2. HDU 4336 Card Collector &lpar;期望DP&plus;状态压缩 或者 状态压缩&plus;容斥&rpar;

    题意:有N(1<=N<=20)张卡片,每包中含有这些卡片的概率,每包至多一张卡片,可能没有卡片.求需要买多少包才能拿到所以的N张卡片,求次数的期望. 析:期望DP,是很容易看出来的,然后由 ...

  3. hdu 4336 Card Collector&lpar;期望 dp 状态压缩&rpar;

    Problem Description In your childhood, people in the famous novel Water Margin, you will win an amaz ...

  4. HDU 1074 Doing Homework(DP状态压缩)

    题意:有n门功课需要完成,每一门功课都有时间期限以及你完成所需要的时间,如果完成的时间超出时间期限多少单位,就会被减多少学分,问以怎样的功课完成顺序,会使减掉的学分最少,有多个解时,输出功课名字典序最 ...

  5. BestCoder Round &num;52 &lpar;div&period;2&rpar; HDU 5418 Victor and World &lpar;DP&plus;状态压缩&rpar;

    [题目链接]:pid=5418">click here~~ [题目大意]: 问题描写叙述 经过多年的努力,Victor最终考到了飞行驾照. 为了庆祝这件事,他决定给自己买一架飞机然后环 ...

  6. hdu 4057 AC自己主动机&plus;状态压缩dp

    http://acm.hdu.edu.cn/showproblem.php?pid=4057 Problem Description Dr. X is a biologist, who likes r ...

  7. hdu 4352 数位dp &plus; 状态压缩

    XHXJ's LIS Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total ...

  8. hdu&lowbar;4352&lowbar;XHXJ&&num;39&semi;s LIS&lpar;数位DP&plus;状态压缩&rpar;

    题目连接:hdu_4352_XHXJ's LIS 题意:这题花大篇篇幅来介绍电子科大的一个传奇学姐,最后几句话才是题意,这题意思就是给你一个LL范围内的区间,问你在这个区间内最长递增子序列长度恰为K的 ...

  9. 【bzoj1076】&lbrack;SCOI2008&rsqb;奖励关 期望dp&plus;状态压缩dp

    题目描述 你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关.在这个奖励关里,系统将依次随机抛出k次宝物,每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再 ...

  10. hdu4336 Card Collector&lpar;概率DP&comma;状态压缩&rpar;

    In your childhood, do you crazy for collecting the beautiful cards in the snacks? They said that, fo ...

随机推荐

  1. VadRoot枚举进程模块在Windows7下的完整实现

      原理小伟的小伟在http://bbs.pediy.com/showthread.php?t=66886说的挺清楚了,Windows7下有一些变化,使用NtQueryVirtualMemory来枚举 ...

  2. synchronized同步锁&plus;单利模式

    public static synchronized VolleyRequestController getInstance() {         if (sInstance == null) { ...

  3. This transaction has been rolled back&comma; rather than only the current&period;

    今天上午,收到运维组同事反映某应用系统的其中一个功能报错,不是偶然性事件,每个使用该功能的用户都报错.报错内容为:This transaction has been rolled back, rath ...

  4. KeyDown&comma;KeyPress 和KeyUp

    研究了一下KeyDown,KeyPress 和KeyUp ,发现之间还是有点学问的.让我们带着如下问题来说明,如果你看到这些问题你都知道,那么这篇文章你就当复习吧:) 1.这三个事件的顺序是怎么样的? ...

  5. PHP根据URL提取根域名

    <?php #使用示例 echo getBaseDomain('http://blog.jp.goo.ne.jp/index.php')->domain;echo "\n&quo ...

  6. 常见的XSS攻击代码

    第一类: <tag on*=*/> 在html标签事件中触发,典型的是on*事件,但是这种触发模式的缺陷在于不能直接触发所以更多的需要配合使用. eg: 1.使html元素占据整个显示页面 ...

  7. Android Api 检查參数状态Api

    转载请注明出处:http://blog.csdn.net/droyon/article/details/39938677 在进行Android应用程序开发中,android提供了一个非常好的工具类,来 ...

  8. Python中操作ini配置文件

    这篇博客我主要想总结一下python中的ini文件的使用,最近在写python操作mysql数据库,那么作为测试人员测试的环境包括(测试环境,UAT环境,生产环境)每次需要连接数据库的ip,端口,都会 ...

  9. gitlab 同步小脚本

    gitlab 是公司中的代码仓库,如何保证两台机器同步呢 公司中使用的是docker那么久使用docker进行演示了也方便以后的工作查找资料 附:脚本 #!/bin/bash docker stop ...

  10. Maven私服安装及配置——&lpar;十二&rpar;

    0.私服实际是B/S架构的,需要通过浏览器访问.访问地址在 nexus-2.12.0-01\conf\nexus.properties中查看.