算法：单调队列优化DP
题意
不做赘述。
但是可以想象成一个双方玩博弈的过程， A 取当前区间的一个数（位置为 (i) ((l le i < r))）花 (a_i) ，将这个区间分成 ([l,i]) 和 ([i+1,r]) ，B根据计算选两个区间中一个区间使 A 最后花更多的钱，而 A 要花更少的钱。
注意 (a_i) 非严格单调递增。
思路
- 20pts
可以很容易的想到一个 (O(N^3)) 的区间DP：
(min) 代表 A 主观选最小的， (max) 为 B 主观选两个区间中更大价值的区间。
其中 (f[i][i+1]=a_i) ，(f[i][i]=0) 。
- 100pts
考虑优化，首先总有 (f[i][j]le f[i][j+1]) （显然，但不好证QwQ） (a_i) 是非严格单调递增的，那么在这个式子送，如果能枚举一个下标，将 (f[i][j]) 变成一个在 (i) 或 (j) 意义下的一维数组，既然是单调的是否可以考虑单调队列？
但是这个 (max) 操作有点限制我们。
但因为f有单调性，我们知道随着 (k) 变大 (f[i][k]) 变大， (f[k+1][j]) 变小，也就是说我们可以找到一个点 (p) 对于 ((i,j)) 来说 (f[i][k]) 恰好大于 (f[k+1][j]) 的 (k) 点，而 (p) 右边 (max) 的值选后者， (p) 左边选前者。
联系第一段话，我们现在有两种选择：
- 固定（优先枚举） (i) ，再枚举 (j)
- 固定（优先枚举） (j) ，再枚举 (i)
在枚举第二关键字的过程中 (p) 点应是可从上一个 (p) 点单向移动得到的，具过程体可以手玩得到。
后将 ([i,j]) 分为 ([p,j]) 和 ([i,p-1]) 分别考虑每个点的贡献：
- ([p,j]) 贡献为 (min{f[i][k]+a_k}) 因为随着 (k) 的增加 (a_k) 和 (f[i][k]) 单调递增，显然的贡献为 (f[i][p]+a_p) 。
- ([1,p-1]) 贡献为 (min{f[k][j]+a_k}) ，然而这里就有
大问题了， (a_k) 和 (f[k][j]) 的单调方向相反，难搞。
对于第二类情况，（呼应开头）因为变量只有两个，考虑固定其中一个，再枚举另一个，用单调队列维护。
所以只能固定 (j) （我因为这个搞不懂弄了半天），枚举 (i) 。
至此问题基本解决。
反思
重点：
- 要能想到 (f[i][j]le f[i][j+1]) ，别老是对一个解释不清但显然成立的东西要证明，有些东西就是难以解释。
- 必须将 (j) 作为第一关键字，这是罕见的一道题吧，挺神的。
- 要顺序从 (1) 开始枚举 (j) ，倒序从 (j) 开始枚举 (i) （其他方法都不行）。
最好自己手推一下，可以参考下代码。
代码
主体挺短的，但是写起来真的很难受。
int t, a, s[N + 10], f[N + 10][N + 10], mid[N + 10], l, r, qu[N + 10]; //(mid就是文中的p)
signed main()
{
// freopen("in1.in", "r", stdin);
t = read();
while (t--)
{
a = read();
for (int i = 0; i <= a + 1; i++)
for (int j = 0; j <= a + 1; j++)
f[i][j] = 1e18;
for (int i = 1; i <= a; i++)
s[i] = read();
for (int i = 1; i <= a; i++)
f[i][i] = 0, f[i][i + 1] = s[i];
for (int j = 3; j <= a; j++)
{
mid[j - 1] = j - 1;
l = 1;
r = 0;
for (int i = j - 2; i >= 1; i--)
{
mid[i] = mid[i + 1];
while (mid[i] > i && f[i][mid[i] - 1] > f[mid[i]][j])
mid[i]--;
while (l <= r && qu[l] >= mid[i])
l++;
f[i][j] = min(f[i][j], f[i][mid[i]] + s[mid[i]]);
if (l <= r)
f[i][j] = min(f[i][j], f[qu[l] + 1][j] + s[qu[l]]);
while (l <= r && f[i + 1][j] + s[i] < f[qu[r] + 1][j] + s[qu[r]])
r--;
qu[++r] = i;
}
}
printf("%lld
", f[1][a]);
}
return 0;
}