题解 P1430 【序列取数】

2018-08-22 09:44:53


下面的题解都有点晕啊,我这个菜鸡搞了好久才懂。。。

这个题看上去像个区间DP。

那么设 $f[i][j]$ 表示 $i$ ~ $j$ 这一段区间能取到的最高分。

考虑枚举取到哪里。枚举 $k\in [i,j)$ ,那么可以取 $[i,k]$ 或者 $[k+1,j]$ 。

如果取了左边,那么最高分就是这一段的总分减掉右边的最高分,因为对面必然会把最高分也取掉。 右边同理。

设 $sum$ 为 $i$ ~ $j$ 的和,这个可以前缀和维护。

那么

$$f[i][j]=max_{k=i}^{j-1}(sum,sum-f[k+1][j],sum-f[i][k])$$

最后答案即为 $f[1][n]$ 。

但是这样是 $O(n^3)$ 的,会TLE

考虑优化枚举 $k$ 的循环。我们可以用 $L[i][j]$ 表示 $f[i][i],f[i][i+1],f[i][i+2],...,f[i][j]$ 中的最小值,用 $R[i][j]$ 表示 $f[j][j],f[j-1][j],f[j-2][j],...,f[i][j]$ 中的最小值。

显然 $L[i][j]=min(L[i][j-1],f[i][j])$ , $R[i][j]=min(R[i+1][j],f[i][j])$ 。

那么状态转移方程可以优化为

$$f[i][j]=sum-min(0,L[i][j-1],R[i+1][j])$$

注意边界为 $f[i][i]=L[i][i]=R[i][i]=a[i]$ 。

代码见蒟蒻的blog