CF Round #870 (Div. 2) D. Running Miles 贪心 + 区间dp

感觉好久没写dp了，蓝桥决赛前写点 dp 找找 feel  (doge)。。。

题目地址: https://codeforces.com/contest/1826/problem/D

题目大意: 有一个序列，求一个区间使得区间前三大的值减去(r-l)的值最大，求最大值

思路: 可以使用贪心的思想考虑选择左右边界[l, r], 其中 a[l], a[r] 是改区间前三大值的其中两个, 当然，我们可以假设选取右端点 r 作为前三大值的其中一个, 然后通过 dp 枚举答案， 那么可以设置状态:

dp[i][0] : 从 i 往前选取 0 个数时得到的最大值

dp[i][1] : 从 i 往前选取 1 个数时得到的最大值

dp[i][2] : 从 i 往前选取 2 个数时得到的最大值

dp[i][3] : 从 i 往前选取 3 个数时得到的最大值

下面我们来推导状态转移方程:

对于 dp[i][0], 显然有 dp[i - 1][0]

dp[i][1], 我们可以从当前为开始选, 亦或者是从上一个状态转移过来的(也就是dp[i - 1][1], 又因为区间变长了, 所以为 dp[i - 1][1] - 1):

dp[i][1] = max(dp[i - 1][0] + a[i], dp[i - 1][1] - 1)

同样:

dp[i][2] = max(dp[i - 1][1] + a[i] - 1, dp[i - 1][2] - 1)

dp[i][3] = max(dp[i - 1][2] + a[i] - 1, dp[i - 1][3] - 1)

于是我们就可以枚举右端点 r (从 3 开始) 得到最大值了

时间复杂度: O():