题解：CF1881E Block Sequence

简单 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}

。

综上所述，可得出代码：

CPP

#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;
}

题解：CF1881E Block Sequence

文章操作

相关推荐

评论

题解：CF1881E Block Sequence