注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2964]Boss单挑战  

2015-06-20 17:00:04|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2964: Boss单挑战

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 171  Solved: 77
[Submit][Status][Discuss]

Description

  某RPG游戏中,最后一战是主角单挑Boss,将其简化后如下:
  主角的气血值上限为HP,魔法值上限为MP,愤怒值上限为SP;Boss仅有气血值,其上限为M。
  现在共有N回合,每回合都是主角先行动,主角可做如下选择之一:
  1. 普通攻击:减少对方X的气血值,并增加自身DSP的愤怒值。(不超过上限)
  2. 法术攻击:共有N1种法术,第i种消耗Bi的魔法值,减少对方Yi的气血值。(使用时要保证MP不小于Bi)
  3. 特技攻击:共有N2种特技,第i种消耗Ci的愤怒值,减少对方Zi的气血值。(使用时要保证SP不小于Ci)
  4. 使用HP药水:增加自身DHP的气血值。(不超过上限)
  5. 使用MP药水:增加自身DMP的魔法值。(不超过上限)
  之后Boss会攻击主角,在第i回合减少主角Ai的气血值。
  刚开始时气血值,魔法值,愤怒值都是满的。当气血值小于等于0时死亡。
  如果主角能在这N个回合内杀死Boss,那么先输出“Yes”,之后在同一行输出最早能在第几回合杀死Boss。(用一个空格隔开)
  如果主角一定会被Boss杀死,那么输出“No”。
  其它情况,输出“Tie”。

Input

输入的第一行包含一个整数T,为测试数据组数。
接下来T部分,每部分按如下规则输入:
第一行九个整数N, M, HP, MP, SP, DHP, DMP, DSP, X。
第二行N个整数Ai。
第三行第一个整数N1,接下来包含N1对整数Bi, Yi。
第四行第一个整数N2,接下来包含N2对整数Ci, Zi。

Output

输出共包含T行,每行依次对应输出一个答案。

Sample Input

2 5 100 100 100 100 50 50 50 20 50 50 30 30 30 1 100 40 1 100 40 5 100 100 100 100 50 50 50 10 50 50 30 30 30 1 100 40 1 100 40

Sample Output

Yes 4 Tie 样例说明   对于第一个样例,主角的策略是:第一回合法术攻击,第二回合使用HP药水,第三回合特技攻击,第四回合普通攻击。

HINT

对于100%的数据:1 ≤ N ≤ 1000,1 ≤ M ≤ 1000000,1 ≤ HP,MP,SP ≤ 1000,N1,N2 ≤ 10,DHP,Ai ≤ HP,DMP,Bi ≤ MP,DSP,Ci ≤ SP,X,Yi,Zi ≤ 10000,1 ≤ T ≤ 10。

Source

Solution

题意:

主角的气血值上限为HP,魔法值上限为MP,愤怒值上限为SP;Boss仅有气血值,其上限为M。

  现在共有N回合,每回合都是主角先行动,主角可做如下选择之一:

  1.减少对方X的气血值,并增加自身DSP的愤怒值。(不超过上限)

  2.共有N1种法术,第i种消耗Bi的魔法值,减少对方Yi的气血值。(使用时要保证MP不小于Bi)

  3.共有N2种特技,第i种消耗Ci的愤怒值,减少对方Zi的气血值。(使用时要保证SP不小于Ci)

  4.增加自身DHP的气血值。(不超过上限)

  5.增加自身DMP的魔法值。(不超过上限)

  之后Boss会攻击主角,在第i回合减少主角Ai的气血值。

  刚开始时气血值,魔法值,愤怒值都是满的。当气血值小于等于0时死亡。

  如果主角能在这N个回合内杀死Boss,那么先输出“Yes”,之后在同一行输出最早能在第几回合杀死Boss。(用一个空格隔开)

  如果主角一定会被Boss杀死,那么输出“No”。

  其它情况,输出“Tie”。

对于100%的数据:1 ≤ N ≤ 1000,1 ≤ M ≤ 1000000,1 ≤ HP,MP,SP ≤ 1000,N1,N2 ≤ 10,DHP,Ai ≤ HP,DMP,Bi ≤ MP,DSP,Ci ≤ SP,X,Yi,Zi ≤ 10000,1 ≤ T (数据组数)≤ 10。

  

分析:我们注意到,与SP相关的事件只有两个(1,3),与MP相关的事件只有两个(2,5),并且互相独立,与回合无关,那么我们可以用Mp[i][j]表示用了i个回合(只考虑与MP相关的事件),当前MP为j时能造成的最大伤害,那么就可以写出Mp的转移方程:

Mp[i + 1][min(MP, j + DMP)] = max(Mp[i][j], Mp[i + 1][min(MP, j + DMP)]);

for (k = 1; k <= N1; k++) 

   if (j >= B[k]) 

     Mp[i + 1][j - B[k]] = max(Mp[i][j] + Y[k], Mp[i + 1][j - B[k]]); 

接下来,我们用L1[i]表达用了i回合,只用Mp攻击能造成的最大伤害,L1[i]=max(Mp[i][j])(j >= 0)

同理,处理出L2表示用了i回合,只用Sp攻击能造成的最大伤害,将L1,L2合并为L,L[i]表示用了i回合,造成的最大伤害,L[i+j]=max(L[i]+L[j])

这样,我们就知道了与伤害有关的全部信息;

同样,我们用F[i][j]表示前i回合,当前Hp为j时,能用来攻击的回合数(就是保证不死尽量多打),然后用H[i]表示前i回合,不死能打多少回合:

H[i + 1] = max(H[i + 1], F[i][j] + 1);(因为主角先动,我们可以在本回合内打死Boss) 

H[i + 1] = max(H[i + 1], F[i + 1][j]);

这样,就可以容易的判断出最早在第几回合能打死Boss了

时间复杂度:O(T*N*(HP+MP+SP+N))

Code

/**************************************************************
    Problem: 2964
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:2124 ms
    Memory:12800 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define cmax(a,b) (a<b?a=b:1)
#define N 1010
#define M(a) memset(a,-63,sizeof(a))
int mp[N][N],sp[N][N],l1[N],l2[N],l[N],f[N],hp[N][N],a[N],i,j,k,ans,flag,tmp;
int _,n,m,HP,MP,SP,DHP,DMP,DSP,X,B[N],C[N],Y[N],Z[N],n1,n2,aa;
char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
int main(){
    for(_=F();_--;){
        flag=0;
        n=F(),m=F(),tmp=HP=F(),MP=F(),SP=F(),DHP=F(),DMP=F(),DSP=F(),X=F();
        for(i=1;i<=n;i++)a[i]=F();
        for(n1=F(),i=1;i<=n1;i++)B[i]=F(),Y[i]=F();
        for(n2=F(),i=1;i<=n2;i++)C[i]=F(),Z[i]=F();
        M(mp),M(sp),M(hp),M(l1),M(l2),M(l),M(f);
        //mp
        mp[0][MP]=0;
        for(i=0;i<n;i++)
        for(j=0;j<=MP;j++){
            cmax(mp[i+1][min(j+DMP,MP)],mp[i][j]);
            for(k=1;k<=n1;k++)
            if(j>=B[k])cmax(mp[i+1][j-B[k]],mp[i][j]+Y[k]);
        }
        for(i=0;i<=n;i++)
        for(j=0;j<=MP;j++)cmax(l1[i],mp[i][j]);
        //sp
        sp[0][SP]=0;
        for(i=0;i<n;i++)
        for(j=0;j<=SP;j++){
            cmax(sp[i+1][min(j+DSP,SP)],sp[i][j]+X);
            for(k=1;k<=n2;k++)
            if(j>=C[k])cmax(sp[i+1][j-C[k]],sp[i][j]+Z[k]);
        }
        for(i=0;i<=n;i++)
        for(j=0;j<=SP;j++)cmax(l2[i],sp[i][j]);
        //mp+sp
        for(i=0;i<=n;i++)
        for(j=0;i+j<=n;j++)
        cmax(l[i+j],l1[i]+l2[j]);
        //hp
        hp[1][HP]=1;
        for(i=1;i<=n;i++)
        for(j=a[i]+1;j<=HP;j++){
            cmax(hp[i+1][min(j+DHP-a[i],HP)],hp[i][j]);
            cmax(hp[i+1][j-a[i]],hp[i][j]+1);
        }
        for(i=1;i<=n+1;i++)
        for(j=1;j<=HP;j++)
        cmax(f[i],hp[i][j]);
        for(i=1;i<=n&&flag==0;i++)
        if(f[i]>0&&l[f[i]]>=m)flag=1,ans=i;
        for(i=1;i<=n&&flag==0;i++){
            tmp=min(tmp+DHP,HP);
            if(tmp-a[i]<=0)flag=-1;tmp-=a[i];
        }
        if(flag==1)printf("Yes %d\n",ans);
        else if(flag==-1)printf("No\n");
        else puts("Tie");
    }
}
  评论这张
 
阅读(186)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018