AT_dp_l 题解

---

知识前置

双端队列

双端队列是指一个可以在队首或队尾插入或删除元素的队列。相当于是栈与队列功能的结合。

区间DP

详见OI-Wiki。

---

题目描述

给一个双端队列，双方轮流取数，每一次能且只能从队头或队尾取数，取完数后将这个数从队列中弹出。双方都希望自己取的所有数之和尽量大，且双方都以最优策略行动，假设先手取的所有数之和为 $X$，后手取的所有数之和为 $Y$，求 $X-Y$。

数据范围：$1\le N\le3000$，$1\le a_i\le1\times10^9$

---

解题思路

正确性证明

该问题满足最优性原则和无后效性原则，同时数据范围允许使用动态规划，所以考虑区间DP求解。

状态设置

由题意得，剩下的数都是连续的。
设$f[i][j]$表示剩下从$i$到$j$这些数时，先手与后手分数的差。注意此时的先手是开始时的先手，不是当前先手。

状态转移

一个长区间的状态可以由其内部更短区间的状态转移得到。具体地，一个区间$[i,\ j]$的状态可以由区间$[i+1,\ j]$和$[i,\ j-1]$转移得到，转移时只需要判断$a[i]$与$a[j]$即可。

原序列长度为$n$，没有取到的数位于区间$[i,\ j]$内，所以已经取过的数总共$(n+i-j-1)$个

如果已经取走的数的有偶数个，那新的数将被先手取到。状态设置的是先手与后手的分数差，所以当先手取到新数时，这个差值会变大。
如果这个数从队头取，原先没有被选的区间$[i,\ j]$变为$[i+1,\ j]$，同时答案加上$a[i]$。
如果这个数从队尾取，原先没有被选的区间$[i,\ j]$变为$[i,\ j-1]$，同时答案加上$a[j]$。
就先手而言，自己得到更大的数的和是最佳决策，即最优解为分数差较大的一个。由于先手按照最优策略决策，这两个答案将取最大值作为新状态。

如果已经取走的数的有奇数个，那新的数将被后手取到。状态设置的是先手与后手的分数差，所以当后手取到新数时，这个差值会变小。
如果这个数从队头取，原先没有被选的区间$[i,\ j]$变为$[i+1,\ j]$，同时答案减去$a[i]$。
如果这个数从队尾取，原先没有被选的区间$[i,\ j]$变为$[i,\ j-1]$，同时答案减去$a[j]$。
就后手而言，自己得到更大的数的和是最佳决策，即最优解为分数差较小的一个。由于后手按照最优策略决策，这两个答案将取最小值作为新状态。

综上，容易得到总的状态转移方程：
$$
f[i][j]=
\begin{cases}
max(f[i+1][j]+a[i],\ f[i][j-1]+a[j]),\ n+i-j-1\equiv0\pmod2\\
min(f[i+1][j]-a[i],\ f[i][j-1]-a[j]),\ n+i-j-1\equiv1\pmod2
\end{cases}
$$

初始状态

由于最开始一个数都没有取时，双方分数都为$0$，分数差为$0$，所以初始值全部为$0$。

代码实现

枚举区间起点和区间长度，长度从$1$到$n$依次枚举，计算对应答案。从全部取完向前倒推，直到开始的时候，即可得出答案。最终答案为$f[1][n]$。

---

AC代码

#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

char buf[1<<20], *p1, *p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)

inline ll read() {
	ll x=0, f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}

#define N 3010
#define e h+i

ll n, d[N], f[N][N];

signed main() {
	n=read();
	for (ll i=1; i<=n; ++i) d[i]=read();
	for (ll i=0; i<n; ++i) {
		for (ll h=1; h<=n-i; ++h) {
			if ((n-i)&1) f[h][e]=max(f[h+1][e]+d[h], f[h][e-1]+d[e]);
			else f[h][e]=min(f[h+1][e]-d[h], f[h][e-1]-d[e]);
		}
	}
	printf("%lld", f[1][n]);
	return 0;
}

---

总结

对于这道题

需要注意倒序计算，并且先手和后手采取的策略不一样，状态转移方程也有所不同。

对于区间DP

1.根据端点设状态，一般二维。
2.状态由区间合并得到。