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模板网!

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

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

相关文章

  • 【图论】Floyd算法

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

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

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

    2024年02月03日
    浏览(36)
  • 图论中的算法

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

    2024年02月08日
    浏览(88)
  • 算法题目题单+题解——图论

    本文为自己做的一部分图论题目,作为题单列出,持续更新。 题单由题目链接和题解两部分组成,题解部分提供简洁题意,代码仓库:Kaiser-Yang/OJProblems。 对于同一个一级标题下的题目,题目难度尽可能做到递增。 题目链接:Luogu P3547 [POI2013] CEN-Price List 题解: 题目链接:

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

    如上图,已知图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日
    浏览(39)
  • 图论相关算法

    迪杰斯特拉算法使用类似广度优先搜索的方法解决了 带权图的单源最短路径问题 。这是一个贪心算法。 注意:此算法只适用于求 有向图 或 边权值非负的无向图 。 1.核心思想 (1)每次选中一个点,这个点满足两个条件: 未被选过 距离最短 (2)对于这个点的所有邻近点都

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

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

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

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

    2024年02月03日
    浏览(41)
  • 算法提高-图论- 最小生成树

    和上题一摸一样,但是题意要求的out看起来需要特别处理,其实只要想清楚kruskal的性质就好 题意就是求最小生成树,因为边权都是正数,那么我们多选一条边必然会导致我们的代价增大 但如果题目说了边权为正或者负数,那么就不是最小生成树了,极端一点所有边都是负的

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

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

    2024年02月11日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包