題目地址: https://codeforces.com/contest/1736/problem/C1

好久沒更新了，本蒟蒻又來發(fā)題解了。。。

題目大概意思是求給定數(shù)組中子序列符合(Good Subarrays)條件的對數(shù), Good Subarrays中每個元素都有大于它的下標(biāo).

一開始的想法是雙指針, 可惜太菜了，在寫代碼過程中遇到很多問題，果斷放棄。。。

那么正確解法是什么呢? 官方給我們整了一手優(yōu)雅的dp:

沒想到可以用動態(tài)規(guī)劃解, 首先定義dp[i] : 以i結(jié)尾最長Good subarrays的長度.

明確dp定義后, 我們需要寫出狀態(tài)轉(zhuǎn)移方程:

首先顯然得出 dp[0]=0

那么dp[i] (i > 0) 該怎么確定呢?

我們可以分情況討論:

當(dāng) a[i] >= dp[i - 1] + 1 時

這時候a[i - dp[i - 1], i - 1]必然是好序列, 現(xiàn)在要觀察a[i - dp[i - 1], i] 是否為好序列, 顯然當(dāng)a[i] >= dp[i - 1] + 1時成立。得出 dp[i] = dp[i-1]+1

當(dāng) a[i] < dp[i? - 1] + 1時,?這時候a[i - dp[i - 1], i - 1]必然是好序列, 現(xiàn)在要觀察a[i?- dp[i?- 1], i] 是否為好序列, 與上面相反, 這時a[i - dp[i - 1], i] 并不是好序列, 于是 dp[i] = a[i]

于是狀態(tài)方程就寫好了:

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

接下來只要把dp數(shù)組所有的值相加就可以啦!!!

代碼: