题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2964

题目分类：动态规划

题意：

无法概括请直接复制题目链接。

题解：

我们可以发现技能攻击，法术攻击和血量处理三种决策类型是分离的，可以分别考虑。

吃红瓶算作血量处理，之和自己的血量有关，普通攻击和技能攻击算作技能攻击，之和自己的怒气有关，吃蓝瓶和法术攻击算作法术攻击，只和自己的法力有关。

这三个部分可以分别dp。

对于血量处理我们需要知道吃红瓶对于战斗的唯一有意义的数据在于n回合内要用多少回合吃红瓶才能不死，这个可以使用回合数和当前血量做下标，状态表示最少的吃药回合数，决策为吃药或者不吃药。

对于技能攻击我们需要计算在n回合内最多可以给对方造成多少伤害，可以使用回合数和当前怒气作为下标，状态表示最大伤害制造值，决策为普通攻击和发动技能。

对于法术攻击我们使用和技能攻击相似的方式处理。

最后枚举多少回合可以结束战斗，回合数减去吃红瓶的回合数就是攻击回合数，再枚举多少回合法术攻击，剩下的技能攻击，判断是否击杀对手，如果在这之前没有击杀对手而在这一回合必然被击杀则负。

需要注意的是，不能进行从后往前的dp，因为上限的存在，后面的状态可以通过前面的多种状态转移而来，需要使用从前往后的顺推方式做动态规划。

同时要注意上限对转移的影响。

程序：

#include<cstdio>
#include<algorithm>
using namespace std;
long long T,n,m,n1,n2,hp,mp,sp,dhp,dmp,dsp,X;
long long a[1200],b[1200],c[1200],y[1200],z[1200];
long long f13[1200][1200],f25[1200][1200],f4[1200][1200],d13[1200],d25[1200],d4[1200];
inline bool checkwin(long long x)
{
	x-=d4[x-1];
	for (long long i=0;i<=x;i++)
	{
		if(d13[i]+d25[x-i]>=m)return true;
	}return false;
}
inline bool checklose(long long x)
{
	if(d4[x]>=100000)return true;
	return false;
}
int main()
{
	scanf("%lld",&T);
	while (T--)
	{
		scanf("%lld%d%d%d%d%d%d%d%d",&n,&m,&hp,&mp,&sp,&dhp,&dmp,&dsp,&X);
		for (long long i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
		}
		scanf("%lld",&n1);
		for (long long i=1;i<=n1;i++)
		{
			scanf("%lld %lld",&b[i],&y[i]);
		}
		scanf("%lld",&n2);
		for (long long i=1;i<=n2;i++)
		{
			scanf("%lld %lld",&c[i],&z[i]);
		}
		for (long long i=0;i<=1000;i++)
		{
			d13[i]=0;
			d25[i]=0;
			d4[i]=100000000;
			for (long long j=0;j<=1000;j++)
			{
				f13[i][j]=-100000000;
				f25[i][j]=-100000000;
				f4[i][j]=100000000;
			}
		}
		f4[0][hp]=0;d4[0]=0;
		for (long long i=0;i<=n;i++)
		{
			for (long long j=1;j<=hp;j++)
			{
				if(f4[i][j]>10000)continue;
				long long cs=max(min(hp,j+dhp)-a[i+1],0LL);
				f4[i+1][cs]=min(f4[i+1][cs],f4[i][j]+1);
				cs=max(j-a[i+1],0LL);
				f4[i+1][cs]=min(f4[i+1][cs],f4[i][j]);
				d4[i]=min(d4[i],f4[i][j]);
		//		printf("%lld %lld %lld %lld\n",i,j,d4[i],f4[i][j]);
			}
		}
		f13[0][sp]=0;
		for (long long i=0;i<=n;i++)
		{
			for (long long j=0;j<=sp;j++)
			{
				if(f13[i][j]<0)continue;
				long long cs=min(j+dsp,sp);
				f13[i+1][cs]=max(f13[i+1][cs],f13[i][j]+X);
				for (long long k=1;k<=n2;k++)
				{
					if(j>=c[k])f13[i+1][j-c[k]]=max(f13[i+1][j-c[k]],f13[i][j]+z[k]);
				}
				d13[i]=max(d13[i],f13[i][j]);
			//	printf("%lld %lld %lld\n",i,j,f13[i][j]);
			}
		}
		f25[0][mp]=0;
		for (long long i=0;i<=n;i++)
		{
			for (long long j=0;j<=mp;j++)
			{
				if(f25[i][j]<0)continue;
				long long cs=min(j+dmp,mp);
				f25[i+1][cs]=max(f25[i+1][cs],f25[i][j]);
				for (long long k=1;k<=n1;k++)
				{
					if(j>=b[k])f25[i+1][j-b[k]]=max(f25[i+1][j-b[k]],f25[i][j]+y[k]);
				}
				d25[i]=max(d25[i],f25[i][j]);
			//	printf("%lld %lld %lld\n",i,j,f13[i][j]);
			}
		}
		for (long long i=1;i<=n;i++)
		{
			d25[i]=max(d25[i],d25[i-1]);
			d13[i]=max(d13[i],d13[i-1]);
		//	printf("%lld %lld %lld %lld\n",i,d4[i],d13[i],d25[i]);
		}
		long long ans=0;
		long long fl=0;
		for (long long i=1;i<=n;i++)
		{
			if(checkwin(i)){fl=1;printf("Yes %lld\n",i);break;}
			if(checklose(i)){fl=1;printf("No\n");break;}
		}
		if(fl==0)printf("Tie\n");
	}
	return 0;
}
/*
2
5 10 10 10 10 5 5 5 2
5 5 3 3 3
1 10 4
1 10 4
5 10 10 10 10 5 5 5 1
5 5 3 3 3
1 10 4
1 10 4
*/