Acwing 180.排书 （IDEA*）
2020-12-26 09:27
标签：turn ++ 状态 代码 回溯 using end 输入格式 区间 给定n本书，编号为1-n。 在初始状态下，书是任意排列的。 在每一次操作中，可以抽取其中连续的一段，再把这段插入到其他某个位置。 我们的目标状态是把书按照1-n的顺序依次排列。 求最少需要多少次操作。 输入格式 每组数据包含两行，第一行为整数n，表示书的数量。 第二行为n个整数，表示1-n的一种任意排列。 同行数之间用空格隔开。 输出格式 如果最少操作次数大于或等于5次，则输出”5 or more”。 每个结果占一行。 数据范围 用idea*写，然后这题的朴素枚举是会超时的，当然还有可以使用双向bfs优化，我后面会补。然后，搜索顺序的话，就暴力枚举区间几点和长度，然后去枚举插入的点，去更新数组，这里需要回溯一下。然后我们考虑估价函数，我们可以发现每一次的联结，会断开三个点，联结三个点，最好的情况这三个点先开始全是非法的，交换之后变成合法的，那么我们的估价函数就变成了非法的点数除上3向上取整，这里一个小技巧等价于+2除以3向下取整。 Acwing 180.排书 （IDEA*） 标签：turn ++ 状态 代码 回溯 using end 输入格式 区间 原文地址：https://www.cnblogs.com/hhlya/p/13379745.html题面
第一行包含整数T，表示共有T组测试数据。
每组数据输出一个最少操作次数。
1≤n≤15
输入样例：
3
6
1 3 4 6 2 5
5
5 4 3 2 1
10
6 8 5 3 4 7 2 9 1 10
输出样例：
2
3
5 or more思路
代码实现
#include
文章标题：Acwing 180.排书 （IDEA*）
文章链接：http://soscw.com/index.php/essay/38316.html