admin管理员组

文章数量:1590745

A

思路：

（1）对于每一个位置，有三种选择，一是选择删除，二是选择当排头清洗，三是被前面的排头清洗；

（2）注意到总是要求将最后一位数清洗完，即前面信息依赖后面信息，于是考虑从后往前分析，令f[i]描述i~n最小代价，则对于第i位，可选择

  1. 删除: f[i] = f[i +1] + 1；
  2. 清洗：f[i] = f[i + a[i] + 1]
  3. 等待清洗：由于我们只讨论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

版权声明：本文标题：A 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dongtai/1717065320a531399.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。