自做网站图片版权,盗号网站怎么做,wordpress 多用户样式,无极网站站怎么有的下不了原题链接
题目描述
给定 n 本书#xff0c;编号为 1∼n。 在初始状态下#xff0c;书是任意排列的。在每一次操作中#xff0c;可以抽取其中连续的一段#xff0c;再把这段插入到其他某个位置。我们的目标状态是把书按照 1∼n 的顺序依次排列。求最少需要多少次操作。
输…原题链接
题目描述
给定 n 本书编号为 1∼n。 在初始状态下书是任意排列的。在每一次操作中可以抽取其中连续的一段再把这段插入到其他某个位置。我们的目标状态是把书按照 1∼n 的顺序依次排列。求最少需要多少次操作。
输入格式 第一行包含整数 T表示共有 T 组测试数据。 每组数据包含两行第一行为整数 n表示书的数量。 第二行为 n 个整数表示 1∼n 的一种任意排列。 同行数之间用空格隔开。
输出格式 每组数据输出一个最少操作次数。 如果最少操作次数大于或等于 5 次则输出 5 or more。 每个结果占一行。 数据范围1≤n≤15
样例
in
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
out:
2
3
5 or more 算法 IDA* IDA* 算法即迭代加深的 A* 算法
迭代加深:
不断加深搜索层数
例while(depth5!dfs(0,depth)) {depth; }A*:估价函数
估价函数需要满足不大于实际步数
在最终状态下每本书后面的书的编号应该比当前书多1。
每次移动最多会断开三个相连的位置再重新加入三个相连的位置因此最多会将3个错误的连接修正
所以如果当前有 sum次操作。因此当前状态 u 的估价函数可以设计成 f(u)sum/3;
如果当前层数加上 f(s)大于迭代加深的层数上限则直接returnint f() {int sum 0;for(int i 0 ; i n -1 ; i) {if(a[i1]!a[i]1) sum;}return (sum2)/3;
}if (depth f() max_depth) return false;参考文献
作者yxc 链接题解
代码 #includebits/stdc.h
using namespace std;
const int N 20;
int a[N],t[5][N];
int n,T;
int f() {int sum 0;for(int i 0 ; i n -1 ; i) {if(a[i1]!a[i]1) sum;}return (sum2)/3;
}
bool dfs(int depth, int max_depth)
{if (depth f() max_depth) return false;if (f()0) return true;for(int len 1; len n ; len) {for(int l 0; l len - 1 n; l) {int r l len - 1;for(int k r 1; k n ;k) {memcpy(t[depth], a, sizeof a);int x l;for(int y r 1; y k; y,x) a[x] t[depth][y];for(int y l; y r; y,x) a[x] t[depth][y];if (dfs(depth 1, max_depth)) return true;memcpy(a, t[depth], sizeof a);}}}return false;
}int main() {cinT;while(T--) {cinn;for(int i 0 ; i n ; i) cina[i];int depth 0;while(depth5!dfs(0,depth)) {depth; }if(depth5) cout5 or more\n;else coutdepthendl;}
}
