CF1881E Block Sequence

序列dp

题目大意

有 $n$ 个元素，第 $i$ 个元素是 $a_i$。一个合法的块的长度必须是块的第一个元素 $+1$ 的值，而你可以删除若干个元素。问你最少需要删除多少个元素才能使得这 $n$ 个元素可以分成若干个块的组合。

思路

看到题目，可能会想到贪心？二分？但是观察样例，如果是贪心的话我们并不能使用一种每次都必定最优的算法，而我们也不能高效地判断一个解是否合法。那么，压力就来到了 dp 这边。

正着操作显然非常麻烦，那么我们就反向操作。我们设 $d{p}_i$ 表示为把 $i$ 当作第一个块的第一个元素，最少需要更改多少次。那么对于元素 $a_i$，我们可以选择舍去或是保留。舍去就很简单了，直接保留 $d{p}_{(i+1)}$ 的值并 $+1$；如果保留，那么当前块的长度就是 $a_i$，块后面的第一个元素就是，$d{p}_{(i+a_i+1)}$。因此状态转移方程就是：

$$d{p}_i=\min (d{p}_{(i+1)}+1,d{p}_{(i+a_i+1)})$$

代码

#include <iostream>
 
using namespace std;
 
const int kMaxN = 2e5 + 5;
 
int a[kMaxN], dp[kMaxN], t, n;
 
int main() {
  for (cin >> t; t; t--) {
    cin >> n, dp[n + 1] = 0;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    dp[n] = a[n] != 0;
    for (int i = n - 1; i >= 1; i--) {
      if (i + a[i] <= n) {
        dp[i] = min(dp[i + 1] + 1, dp[i + a[i] + 1]);
      } else {
        dp[i] = dp[i + 1] + 1;
      }
    }
    cout << dp[1] << '\n';
  }
  return 0;
}