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;
}
标签:903,Sequence,int,Codeforces,long,Block,Div,dp
From: https://www.cnblogs.com/ikunhuaji/p/17764110.html