思路:
(1)对于每一个位置,有三种选择,一是选择删除,二是选择当排头清洗,三是被前面的排头清洗;文章来源:https://www.toymoban.com/news/detail-719374.html
(2)注意到总是要求将最后一位数清洗完,即前面信息依赖后面信息,于是考虑从后往前分析,令f[i]描述i~n最小代价,则对于第i位,可选择文章来源地址https://www.toymoban.com/news/detail-719374.html
- 删除: f[i] = f[i +1] + 1;
- 清洗:f[i] = f[i + a[i] + 1]
- 等待清洗:由于我们只讨论i~n位的信息,所以必须保证第i位被清洗,故不可等待。
代码:
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 2e5 + 10;
int dp[maxn], a[maxn];
void solve() {
int n;
cin >> n;
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] = 1 + dp[i+1]; // 删除第i个
if (i + a[i] <= n) { // 利用第i个做为区间起点
dp[i] = min(dp[i], dp[i+a[i]+1]);
}
}
printf("%d\n", dp[1]);
}
int main()
{
int t;
cin >> t;
while(t --)
{
solve();
}
return 0;
}
到了这里,关于A - Block Sequence的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!