Bags Game

题目传送门

引

这种博弈问题挺经典的,第一时间就应该想到 $区间DP$ ,小小地积累一下吧

解法

设计出 $DP$
$$f_{l.r}:考虑区间[l,r].先手可以获得的最大差值$$
应该有些题也可以定义为 最大值 , 计算答案时用 总和 算出 差值 , 但是这道不行,计算中途可能减去 $A$ 或 $C$ 不好记录

考虑转移

1. 直接取两端：
   显然有 $f_{l,r}\leftarrow \max (a_l-f_{l+1,r},a_r-f_{l,r-1})$

2. 给 $Snuke$ 钱
   $f_{l,r}\leftarrow s_{l,r}-A/C-(f_{i,i-1+B/D}+s_{i,i-1+B/D})$
   用个数据结构或单调队列维护好 $f_{i,i-1+B/D}+s_{i,i-1+B/D}$ 的最小值就好了

Code

用的单调队列

#include
#define S(p,q) s[p+q-1]-s[q-1]
#define V(p,q) (S(p,q)+f[p][q])

using ll = long long ;
using namespace std;

const int N=3e3+7;
ll f[N][N],n,A,B,C,D,s[N],x[N],q[N];
void calc(ll k,ll i,ll Z){
	for(ll j=1,h=1,t=0;j<=n+1-k;j++){
		while(h<=t&&V(k,q[t])>=V(k,j))t--;
		q[++t]=j;
		while(hi)f[i][j+k-i]=max(f[i][j+k-i],S(i,j+k-i)-Z-V(k,q[h]));
	}
}
int main(){
	scanf("%d %lld %lld %lld %lld",&n,&A,&B,&C,&D);
	for(ll i=1;i<=n;i++) scanf("%lld",&x[i]),s[i]=s[i-1]+x[i];
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=n+1-i;j++)f[i][j]=max(x[j]-f[i-1][j+1],x[i+j-1]-f[i-1][j]);
		calc(i-min(i,B),i,A);calc(i-min(i,D),i,C);
	}
	printf("%lld\n",f[n][1]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

结

好难呀。。