A - Block Sequence

这篇具有很好参考价值的文章主要介绍了A - Block Sequence。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

思路:

(1)对于每一个位置,有三种选择,一是选择删除,二是选择当排头清洗,三是被前面的排头清洗;

(2)注意到总是要求将最后一位数清洗完,即前面信息依赖后面信息,于是考虑从后往前分析,令f[i]描述i~n最小代价,则对于第i位,可选择文章来源地址https://www.toymoban.com/news/detail-719374.html

  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 - Block Sequence的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图论中的算法

    图论的概念 :图论是数学的一个分支,它是以图为研究对象,图论中的图是由若干个给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些实体之间的某种特定的关系,用点代表实体,用连接两点之间的线表示两个实体之间具有某种关系。 图的分类: 无权无向

    2024年02月08日
    浏览(87)
  • 【图论】最短路算法

    不能处理边权为负的情况, 复杂度O(nlogn) 步骤与基本思路 (1)初始化距离数组dist[N],将其所有值赋为0x3f,并将起点1的dist初始化为0,存入优先队列heap中 (2)从所有 未被遍历 的点中找到与起点1的 距离dist[i]最小 的点,并将该点标记为已遍历 (3)利用刚刚遍历的这个点

    2024年02月16日
    浏览(39)
  • 算法提高-图论- 负环

    本博客主要介绍spfa求负环 一般用第二种方法 第一种方法如果每个点入队n次,每次入队也要遍历n次,那么时间复杂度就是n 2 第二种方法时间复杂度是n,只要发现最短路边数=n就说明有环了 一篇很好的博客,介绍了求负环的常用方法和原理 这是一个01规划 + 图论问题 判断负

    2024年02月11日
    浏览(45)
  • 算法之图论

    定义 图通常以一个二元组 G=V, E表示,V表示节点集,E表示边集。节点集中元素的个数,称为图的阶。 若图G中的每条边都是没有方向的,称为无向图;每条边是由两个节点组成的无序对,例如节点V1和节点V2之间的边,记为 若图G中的每条边都是有方向的,称为有向图;有向边

    2024年02月16日
    浏览(49)
  • 【图论】kruskal算法

     Kruskal(克鲁斯卡尔)算法是一种用于解决最小生成树问题的贪心算法。 最小生成树是指在一个连通无向图中,选择一棵包含所有顶点且边权重之和最小的树。 下面是Kruskal算法的基本步骤: 将图中的所有边按照权重从小到大进行 排序 。 创建一个空的最小生成树 集合(并

    2024年02月15日
    浏览(35)
  • 《算法竞赛进阶指南》------图论篇

    Telephone Lines 题意:从1到N修一条电缆,有p对电线杆之间是可以连接的,电信公司可以提供k条电缆,其他的由John提供,求john提供的电缆的最长的那根的长度(ret)。 思路:实则是求最短最长的边。 二分结果(sum)。对于 边值sum, 电信公司需要提供电缆。 用djk 计算 1-n 路径上的

    2024年02月03日
    浏览(35)
  • 图论——最短路算法

    如上图,已知图G。 问节点1到节点3的最短距离。 可心算而出为d[1,2]+d[2,3]=1+1=2,比d[1,3]要小。 是一种基于三角形不等式的多源最短路径算法。边权可以为负数 表现为a[i,j]+a[j,k]a[i,k]。 算法思想: 枚举“中转站”(k),“起点”(i),“终点”(j) 设d[i,j]为由i点到j点的最短路径 则  初

    2024年02月13日
    浏览(38)
  • 【算法】复习搜索与图论

    🍎 博客主页:🌙@披星戴月的贾维斯 🍎 欢迎关注:👍点赞🍃收藏🔥留言 🍇系列专栏:🌙 蓝桥杯 🌙请不要相信胜利就像山坡上的蒲公英一样唾手可得,但是请相信,世界上总有一些美好值得我们全力以赴,哪怕粉身碎骨!🌙 🍉一起加油,去追寻、去成为更好的自己!

    2024年02月05日
    浏览(46)
  • 【图论】Floyd算法

     Floyd算法,也称为Floyd-Warshall算法,是一种用于解决所有节点对最短路径问题的动态规划算法。它可以在有向图或带权图中找到任意两个节点之间的最短路径。 Floyd算法的基本思想是通过中间节点逐步优化路径长度。它使用一个二维数组来存储任意两个节点之间的最短路径长

    2024年02月11日
    浏览(47)
  • 【算法设计与分析】图论(桥)

    目录 一、实验目的: 二、内容: 1. 桥的定义 2. 求解问题 3. 算法 三、实验要求 四、实验内容和结果 基准算法 算法思想 伪代码 时间复杂度分析 算法效率测试 并查集 算法思想 伪代码 时间复杂度分析 算法效率测试 并查集(树) 算法思想 伪代码 时间复杂度分析 算法效率测

    2024年02月03日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包