526互联

Codeforces Round 903 (Div. 3) E. Block Sequence（DP）

发布时间 2023-10-14 14:09:31作者: ikunhuaji

Codeforces Round 903 (Div. 3) E. Block Sequence

思路：

设dp[i]为当i~n为完美的最少删除次数

dp[n]=1,dp[n+1]=0;

从后至前对于dp[i]更新

若直接删除当前点，则为 dp[i+1]+1

若不删除 则为 min（dp[i+a[i]+1] , dp[i]）;

i+a[i]+1为a[i]不能覆盖的位置

#define int long long
#define ld long double

using namespace std;

int t;

int dp[200010];
int a[200010];

void op()
{
	int n;
	cin >> n;

	memset(dp, 0x3f, sizeof dp);

	for (int i = 1; i <= n; i++)cin >> a[i];

	dp[n] = 1;
	dp[n + 1] = 0;

	for (int i = n-1; i >=1; i--)
	{
		dp[i] = min(dp[i + 1] + 1, dp[i]);

		if (a[i] + i + 1 <= n+1)
		{
			dp[i] = min(dp[i + a[i] + 1], dp[i]);
		}
	}
	
	cout << dp[1] << endl;
}

signed main()
{
	cin >> t;
	while (t--)
	{
		op();
	}

	return 0;
}