FOI2020算法冬令营提高组第2试详解

发布时间：2021-09-18 09:36

　　本文对2020年福建省算法冬令营数学专题上的三道测试题作了较为详细的描述与解答。 

【文章来源】：福建电脑. 2020,36(03)

【文章页数】：5 页

【部分图文】：

反悔策略

一排楼房才能满足计划图的要求？n,h≤1,000,0001.2解题思路考虑隐式图。图中的每一个结点表示一个当前的搭建状态。一个点向另一个点连边当且仅当前一个点对应的状态能够通过一次操作变为后一个点对应的状态。想要找一条从初始状态（即已经做完前0列）到目标状态（已经做完前n列）的最短路。图很大，直接找最短路无异于暴搜。可以考虑一些在图上走的策略。图1隐式图考虑在图上贪心地乱走，可能会走到某一个奇怪的点，那么这个点可能根本无法以最短路到达终点，显然不可龋图2贪心处理隐式图的问题图3增加朴素反悔边的隐式图那如果在图中加上边权为对应边的边权的相反数的反悔边呢？那么不论在图上怎么乱走，依然可以有一条最短路能让我们走到终点。但是怎样才能找到这条路呢？因此我们考虑另一种反悔边。它的边权是正整

增加朴素反悔边的隐式图那如果在图中加上边权为对应边的边权的相


本文编号：3399903