http://acm.hdu.edu.cn/showproblem.php?pid=2809
HH大牛出的题目,比赛的时候被唬住了没有去做,今天兴致来了认真敲了一下,秒杀
这题跟1074doing homework一样,位压缩,没的说,自底向上计算,见图

#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;//战斗失败,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 西风萧瑟 阅读(1422) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理