区间dp+博弈论
设j = i+len-1,f[i][len]表示以i为起点，长度为len(j为终点)的区间能取得的最大价值。
状态转移方程：f[i][len] = max(sum[i][j]-f[i+1][len-1],sum[i][j]-f[i][len-1])
即取左面的或者右面的。
博弈论中，双方都要取最优策略$（optimal）$，而且每一轮都可以看作先手和后手的互换。
所以dp方程同时可以表示两个人。
A的价值 = 区间总价值 - B的价值
区间和用前缀和来表示；第二位（区间长度）用滚动数组优化空间。
代码如下
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #define MogeKo qwq using namespace std; const int maxn = 5005; int n,a[maxn],f[maxn][2],s[maxn],ans; int main() { scanf("%d",&n); for(int i = 1; i <= n; i++) scanf("%d",&a[i]); for(int i = 1;i <= n;i++) s[i] = s[i-1]+a[i]; if(n == 1) { printf("%d",a[1]); return 0; } for(int len = 1; len <= n; len++) for(int i = 1; i+len-1 <= n; i++) { int j = i+len-1; f[i][len%2] = max(s[j]-s[i-1]-f[i+1][(len-1)%2],s[j]-s[i-1]-f[i][(len-1)%2]); } printf("%d",f[1][n%2]); return 0; }
Luogu P3004 [USACO10DEC]宝箱Treasure Chest
原文：https://www.cnblogs.com/mogeko/p/11790031.html
