#P1332. Pku3460 Booksort

    ID: 344 传统题 1000ms 128MiB 尝试: 41 已通过: 16 难度: 6 上传者: 标签>CF1900提高IDA*可采纳估价函数估价下界剪枝回溯搜索增量维护添加哨兵

Pku3460 Booksort

题目描述

给定 nn 本书,编号为 1∼n1\sim n。在初始状态下,书是任意排列的。

在每一次操作中,可以抽取其中连续的一段,再把这段插入到其他某个位置。

我们的目标状态是把书按照 1∼n1\sim n 的顺序依次排列。

求最少需要多少次操作。

输入格式

第一行包含整数 TT,表示共有 TT 组测试数据。

每组数据包含两行,第一行为整数 nn,表示书的数量。

第二行为 nn 个整数,表示 1∼n1\sim n 的一种任意排列。

同行数之间用空格隔开。

输出格式

每组数据输出一个最少操作次数。

如果最少操作次数大于或等于 55 次,则输出 5 or more。

每个结果占一行。

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

数据范围

1≤n≤151\le n\le15。本站当前数据版本每个输入文件的测试组数 1≤T≤301\le T\le30。