cf刷题笔记: 1736C1 - Good Subarrays (Easy Version)

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

好久没更新了，本蒟蒻又来发题解了。。。

题目大概意思是求给定数组中子序列符合(Good Subarrays)条件的对数, Good Subarrays中每个元素都有大于它的下标.

一开始的想法是双指针, 可惜太菜了，在写代码过程中遇到很多问题，果断放弃。。。

那么正确解法是什么呢? 官方给我们整了一手优雅的dp:

没想到可以用动态规划解, 首先定义dp[i] : 以i结尾最长Good subarrays的长度.

明确dp定义后, 我们需要写出状态转移方程:

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

那么dp[i] (i > 0) 该怎么确定呢?

我们可以分情况讨论:

当 a[i] >= dp[i - 1] + 1 时

这时候a[i - dp[i - 1], i - 1]必然是好序列, 现在要观察a[i - dp[i - 1], i] 是否为好序列, 显然当a[i] >= dp[i - 1] + 1时成立。得出 dp[i] = dp[i-1]+1

当 a[i] < dp[i  - 1] + 1时, 这时候a[i - dp[i - 1], i - 1]必然是好序列, 现在要观察a[i - dp[i - 1], i] 是否为好序列, 与上面相反, 这时a[i - dp[i - 1], i] 并不是好序列, 于是 dp[i] = a[i]

于是状态方程就写好了:

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

接下来只要把dp数组所有的值相加就可以啦!!!

代码: