首页 > 代码库 > 状态压缩DP----HDU2809
状态压缩DP----HDU2809
状态压缩DP的一道较不错的入门题，第二次做这类问题，感觉不是很顺手，故记录下来.
题目的意思就是吕布战群雄，先给你6个数，分别是吕布的攻击值，防御值，生命值，升级后此三值各自的增量，然后是对手的个数num,接下来是各个对手的名字，攻击值，防御值，生命值，及经验值，规定当吕布经验值每提升100，则攻击值，防御值，生命值加上各自的增量。最后若生命值大于0，输出生命值，否则输出一句话"Poor LvBu,his period was gone."。
刚开始看到此题实在看不出是用压缩DP，以为是普通的DP。但只细一想，状态数太多了并且和编号有关联，原因是：假设与吕布对战的人有三个分别是关羽，张飞，许褚，则现在问题出来了。吕布按什么顺序来对战此三人，吕布-->关羽-->张飞-->许褚，吕布-->张飞-->关羽-->许褚等等，以及战胜一人后生命值是否为零，两人呢.......?这样想着发现很乱很乱，状态多并且不好表示（这不二进制中1正好是状态压缩擅长的嘛）。于是定义状态表达式LvBu[i],i对应的二进制中1代表已和此人对战，如5=101表示分别和关羽，许褚fight了，就差张飞了。但麻烦又来了，101是先和关羽打呢，还是先和许褚打，这里要特别注意的是和谁先打的顺序可能会导致结果不同，例如我先打关羽得到的经验值少不能升级，而我先打许褚升级的经验值就足够了，很明显这两个结果的生命值肯定不会相同。那么怎么解决呢？这只要在for循环时进行更新就可以了
接下来详细解释代码，
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 6 struct Person{ 7 int attck; 8 int defense; 9 int hp;10 int expirence;11 }LvBu[1<<21],Enemy[21],Update;//定义结构体，并分配相应的数组，对手最多20个12 int result,num;13 14 inline int max(int a,int b) //最大值函数15 {16 if(a>b) return a;17 return b;18 }19 20 void Fight()21 {22 int attck,defence;23 int myTime,Time;24 int rHp,expirence,rattack,rdef;25 for(int i=0;i<=result;i++)//状态26 for(int j=0;j<num;j++)//对手编号从0到num-127 {28 if(!(i&(1<<j))&&LvBu[i].hp>0)//若吕布未与编号j对手交战并且生命值不为零，有对战的必要29 {30 attck=max(1,LvBu[i].attck-Enemy[j].defense);//依题目条件吕布攻击一次对方掉attck点血31 defence=max(1,Enemy[j].attck-LvBu[i].defense);//对方攻击一次吕布掉defence点血32 myTime=(LvBu[i].hp+defence-1)/defence;//吕布可以攻击的总次数33 Time=(Enemy[j].hp+attck-1)/attck;//对手可以攻击的总次数34 //如关羽生命值是8,吕布攻击一次造成伤害为-3，那么吕布总共可以攻击3次，那么用一行代码如何表示呢？可以先拿1单位的血出来，剩下的直接除以伤害值35 if(myTime<Time) continue;//吕布先挂了，否则继续执行36 rHp=(LvBu[i].hp-(Time-1)*defence);//剩余生命值原本的减去代价值，Time减一的原因是对手先倒下了，原本你打我一下，我打你一下成偶数的，你走的早就打不到我了37 expirence=Enemy[j].expirence+LvBu[i].expirence;//得到经验值38 rattack=LvBu[i].attck;rdef=LvBu[i].defense;//之所以这样是方便后面书写39 40 if(expirence>=100)//可以升级41 {42 expirence-=100;//付出100点经验值为代价43 rattack+=Update.attck;44 rdef+=Update.defense;45 rHp+=Update.hp;46 }47 48 if(rHp>=LvBu[i|(1<<j)].hp)//这就是我先打许褚-->关羽，还是关羽-->许褚的更新了49 {50 LvBu[i|(1<<j)].attck=rattack;51 LvBu[i|(1<<j)].defense=rdef;52 LvBu[i|(1<<j)].hp=rHp;53 LvBu[i|(1<<j)].expirence=expirence;54 }55 }56 }57 if( LvBu[result].hp) printf("%d\n",LvBu[result].hp);58 else printf("Poor LvBu,his period was gone.\n");59 }60 int main()61 {62 while(scanf("%d %d %d %d %d %d",&LvBu[0].attck,&LvBu[0].defense,&LvBu[0].hp,&Update.attck,&Update.defense,&Update.hp)!=EOF)63 { //输入64 LvBu[0].expirence=0;//吕布初始经验值为065 char name[21];66 scanf("%d",&num);67 for(int i=0;i<num;i++)68 scanf("%s%d%d%d%d",name,&Enemy[i].attck,&Enemy[i].defense,&Enemy[i].hp,&Enemy[i].expirence);69 result=(1<<num)-1;//状态总数70 71 for(int i=1;i<=result;i++) LvBu[i].hp=0;//初始化72 Fight();//对战73 }74 return 0;75 }
以后看着复习就省事多了
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。