P7097-[yLOI2020]牵丝戏【dp】

题目链接:https://www.luogu.com.cn/problem/P7097

有两个人在打游戏，开始时每个人有个初始伤害 x x x和delay值 d d d。

有 m m m种道具，每个道具一个回合只能用一次，可以使当前回合玩家伤害初始伤害的 k i 10000 frac{k_i}{10000} 10000ki​​倍数，并增加该玩家delay值 p i p_i pi​。每个回合 d e l a y delay delay值小的人攻击（相同就第一个人），要求 d e l a y delay delay值差值始终不超过 100 100 100，回合结束时操作的玩家会增加 w w w点delay值。

求双方都最大化自己伤害减去对方伤害的情况下求 n n n个回合后的伤害差。

1 ≤ n ≤ 1 0 3 , 1 ≤ m ≤ 1 0 5 , 1 ≤ w , p i , k i ≤ 100 1leq nleq 10^3,1leq mleq 10^5,1leq w,p_i,k_ileq 100 1≤n≤103,1≤m≤105,1≤w,pi​,ki​≤100

对于这题我的评价是，歌很好听，题出的很好 下次不要再出了 ，就是题面有点长。

实际上还是很简单的，首先道具每个回合是独立的，我们可以先处理出数组 f i f_i fi​表示 i i i点 d e l a y delay delay值会最多增加多少伤害，用背包就好了。

然后剩下的因为 d e l a y delay delay差始终不超过 100 100 100点，设 g i , j g_{i,j} gi,j​表示第 i i i个回合， d e l a y delay delay差为 j j j时的情况，然后根据 j j j倒着转移就好了。

除夕快乐。

时间复杂度： O ( 100 m + 10 0 2 n ) O(100m+100^2n) O(100m+1002n)

#include
#include
#include
#define ll long long
using namespace std;
const ll N=1e3+10,M=1e5+10;
ll T,n,m,d,xa,xb,da,db;
ll k[M],p[M],f[210],g[N][210];
signed main()
{
	scanf("%lld",&T);
	scanf("%lld%lld%lld",&n,&m,&d);
	for(ll i=1;i<=m;i++)scanf("%lld",&k[i]);
	for(ll i=1;i<=m;i++)scanf("%lld",&p[i]);
	scanf("%lld%lld%lld%lld",&xa,&xb,&da,&db);
	for(ll i=1;i<=200;i++)f[i]=-1e9;
	for(ll i=1;i<=m;i++)
		for(ll j=200;j>=p[i];j--)
			if(f[j-p[i]]!=-1e9)
				f[j]=max(f[j],f[j-p[i]]+k[i]);
	for(ll i=1;i<=n;i++)
		for(ll j=0;j<=200;j++){
			if(j<=100){
				g[i][j]=-1e18;
				for(ll k=j+d;k<=200;k++)
					if(f[k-j-d]!=-1e9)g[i][j]=max(g[i][j],g[i-1][k]+xa+xa/100000ll*f[k-j-d]);
			}
			else{
				g[i][j]=1e18;
				for(ll k=0;k<=j-d;k++)
					if(f[j-k-d]!=-1e9)g[i][j]=min(g[i][j],g[i-1][k]-xb-xb/100000ll*f[j-k-d]);
			}
		}
	printf("%lldn",g[n][da-db+100]);
	return 0;
}