n+e

Description

Input

Output

Sample Input

Sample Output

HINT

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");
    }
}