洛谷$P1430$
开坑待补

分析

状态定义：$f[i][j]$表示在$i$、$j$段先手取能得到的最大值
常规版本的状态转移为：

for (int len = 1; len <= n; len ++)
    for (int i = 1; i + len - 1 <= n; i ++)
    {
        int j = i + len - 1;
        // f[i][j]是在$i$、$j$段先手取能得到的最大值，s[j]-s[i-1]减去f[i][k] / f[k][j]即得f[i][j]获得的价值
        for (int k = i; k < j; k ++) f[i][j] = max(s[j] - s[i - 1] - f[i][k], f[i][j]);  // 从右边选去掉[a[i], a[k]](k∈[i, j))的数
        for (int k = j; k > i; k --) f[i][j] = max(s[j] - s[i - 1] - f[k][j], f[i][j]);  // 从左边选去掉[a[k], a[j]](k∈(i, j])的数
    }

对于每一个$f[i][j]$都要枚举从左边和右边选数的分界点$k$，$O(T×n^3)$会$TLE$
这里会用到一个常见的优化枚举$k$的过程的方式，由于$f[i][k]$中的$i$是固定的，因此可以用数组$l[i][j]$来记录$f[i, j]$中$f[i][k]$的最大值，即：
$$l[i][j] = min(l[i][j - 1], f[i][j])$$
因为$l$是用于从左端点开始选数的，因此用$f[i][j]$来更新$l[i][j]$时要和$l[i + 1][j]$取最大值，$l[i + 1][j]$是原来从左开始选取得的最大值
因此每算出一个$f[i][j]$就要用来更新一下$l[i][j]$，同理用$r[i][j]$来记录$f[i, j]$中$f[i][k]$的最大值，即：
$$r[i][j] = min(r[i + 1][j], f[i][j])$$