题目大意：给定一个序列$s$，每个人每轮可以从两端（任选一端）取任意个数的整数，不能不取。在两个人都足够聪明的情况下，求先手的最大得分。

题解：设$f_{i,j}$表示剩下$[i,j]$，先手的最大得分。令$sum_{i,j}=\sum\limits_{k=i}^j s_k$

$$\therefore f_{i,j}=sum_{i,j}-\min\{\min\limits_{k=j-1}^i f_{i,k},\min\limits_{k=i+1}^j f_{k,j},0\}$$

这是$O(n^3)$的，会$TLE$

$$令l_{i,j}=\min\limits_{k=i}^j f_{i,k}, r_{i,j}=\min\limits_{k=i}^j f_{k,j}$$

$$f_{i,j}=sum_{i,j}-\min\{l_{i,j-1},r_{i+1,j},0\}$$

时间复杂度：$O(n^2)$

卡点：无

 

C++ Code：

#include 
     
      #include 
      
       #define maxn 1010using namespace std;int Tim, n;int s[maxn], sum[maxn], f[maxn][maxn];int l[maxn][maxn], r[maxn][maxn];inline int min(int a, int b) {return a < b ? a : b;}inline int max(int a, int b) {return a > b ? a : b;}int main() {	scanf("%d", &Tim);	while (Tim --> 0) {		memset(l, 0x3f, sizeof l);		memset(r, 0x3f, sizeof r);		scanf("%d", &n);		for (int i = 1; i <= n; i++) {			scanf("%d", &s[i]);			sum[i] = sum[i - 1] + s[i];		}		for(int i = 1; i <= n; i++) {			for(int j = i; j; j--) {				int &t = f[j][i], tmp;				t = sum[i] - sum[j - 1];				tmp = min(l[j][i - 1], r[j + 1][i]);				t = max(t, t - tmp);				if(j == i) l[j][i] = r[j][i] = t;				else {					l[j][i] = min(l[j][i - 1], t);					r[j][i] = min(r[j + 1][i], t);				}			}		}		printf("%d\n", f[1][n]);	}	return 0;}