正题
题目链接: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
1\leq n\leq 10^3,1\leq m\leq 10^5,1\leq w,p_i,k_i\leq 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)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#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("%lld\n",g[n][da-db+100]);
return 0;
}
|