感覺好久沒寫dp了，藍(lán)橋決賽前寫點(diǎn)?dp 找找?feel??(doge)。。。

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

題目大意: 有一個(gè)序列，求一個(gè)區(qū)間使得區(qū)間前三大的值減去(r-l)的值最大，求最大值

思路: 可以使用貪心的思想考慮選擇左右邊界[l, r], 其中 a[l], a[r] 是改區(qū)間前三大值的其中兩個(gè), 當(dāng)然，我們可以假設(shè)選取右端點(diǎn) r 作為前三大值的其中一個(gè), 然后通過 dp 枚舉答案， 那么可以設(shè)置狀態(tài):

dp[i][0] : 從 i 往前選取 0 個(gè)數(shù)時(shí)得到的最大值

dp[i][1] :?從 i 往前選取?1?個(gè)數(shù)時(shí)得到的最大值

dp[i][2] :?從 i 往前選取 2?個(gè)數(shù)時(shí)得到的最大值

dp[i][3]?:?從 i 往前選取 3?個(gè)數(shù)時(shí)得到的最大值

下面我們來推導(dǎo)狀態(tài)轉(zhuǎn)移方程:

對(duì)于 dp[i][0], 顯然有 dp[i - 1][0]

dp[i][1], 我們可以從當(dāng)前為開始選, 亦或者是從上一個(gè)狀態(tài)轉(zhuǎn)移過來的(也就是dp[i - 1][1],?又因?yàn)閰^(qū)間變長(zhǎng)了, 所以為 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)

于是我們就可以枚舉右端點(diǎn) r (從 3 開始) 得到最大值了

時(shí)間復(fù)雜度: O():