题解：CF1881E Block Sequence

wangzichen20240101 · 2025-09-20 22:49:20 · 题解

简单 DP 题。

我们定义 dp_i 表示下标从 i 到 n 的子序列的最小操作数。

有两种可能性：

1.由长度为 i 的序列删除一个元素得到 i-1，此时操作次数加一，即 dp_i=dp_{i+1}+1。

2.由长度为 i-a_i-1 的序列加上长度为 a_i+1 的序列组成长度为 i-a_i-1+a_i+1，即 i 的序列，即 dp_i=dp_{i+a_i+1}。

综上所述，可得出代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int T,n,a[N],dp[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> T;
    while(T--){
        memset(dp,0,sizeof(dp));
        cin >> n;
        for(int i = 1;i <= n;++i){
            cin >> a[i];
        }
        if(a[n] == 0) dp[n] = 0;
        else dp[n] = 1;
        for(int i = n - 1;i >= 1;--i){
            dp[i] = dp[i + 1] + 1;
            if(i + a[i] <= n) dp[i] = min(dp[i],dp[i + a[i] + 1]);
        }
        cout << dp[1] << '\n';
    }
    return 0;
}