题解 P2426 【删数】

洛谷题目传送门
一眼看去：区间DP
数据范围：三重循环
好了不装B了，开始说正事
这题非常明显是区间DP。
按照惯例，先定义状态。
分析题目，发现除了区间左端点和右端点之外，什么也不需要加进状态里。因为显而易见除了区间左右端点，没有什么能够影响答案。
所以我们定义状态/(dp[l][r]/)为区间/([l,r]/)的最大答案。
这个“操作价值”可以两重循环预处理出来，所以用/(pre[l][r]/)代表删除区间/([l,r]/)的最大价值。非常明显的，甚至题目里已经直接写明白了， 其实不用预处理，现场算就行，反正是/(O(1)/)的

/[pre[l][r]= /begin{cases} a[l], & /text {$l=r$} // |a[l]-a[r]|/times (r-l+1), & /text{$else$} /end{cases} /]

然后就是最重要的一步——状态转移方程。
题目里有一个操作，就是一个区间删除一些数，失去一些“潜在的”价值。那么把这个过程反过来，一个区间加上

题解 P2426 【删数】最先出现在Python成神之路。