某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”。
输入的第一行包含一个整数T,为测试数据组数。
接下来T部分,每部分按如下规则输入:
第一行九个整数N, M, HP, MP, SP, DHP, DMP, DSP, X。
第二行N个整数Ai。
第三行第一个整数N1,接下来包含N1对整数Bi, Yi。
第四行第一个整数N2,接下来包含N2对整数Ci, Zi。
输出共包含T行,每行依次对应输出一个答案。
对于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。
题意:
主角的气血值上限为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))
/**************************************************************
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"
);
}
}
评论