问题描述

给你一个长为n(n<=15)的序列,你需要将它排序(从小到大)。

你可以从中选取任意一段将它取出,并插入序列中任意位置。问你最少需要多少次这种操作。

输入

第一行给出数据组数T。
每组数据第一行给出n。
接下来一行给出你n个数(这些数是1-n的排列)。

输出

对于每一组数据输出最小的操作次数。
如果操作次数大于或等于5,输出“5 or more”

思路

看数据范围就知道是搜索,而且时限也很宽。

我们分析一下普通的搜索,枚举任意一段共有n*(n-1)/2种情况,枚举插入的位置共有n种情况。所以一次操作就有O(n^3)复杂度,最多要枚举4次操作,所以总复杂度是肯定不符合要求的。

但是我们可以使用IDA* 搜索。假如a[i]+1!=a[i+1]则称这是一个错误后缀,如果一个序列没有错误后缀,则它是有序的。然后我们考虑每一次操作最优只能减少3个错误后缀,所以操作数一定大于等于错误后缀数/3.因此我们将错误后缀数/3作为估值函数。其他的实现就比较简单了。

细节

  1. 循环中变量的范围一定不要弄错了
  2. 估值函数不要写错了,是(cnt+2)/3

代码

#include 
#include 
#include 
#define MAXN 200
using namespace std;

int T, n, a[MAXN], t[MAXN], ans;
bool flag;

int h(int *a)
{
    int cnt=0; 
    for(int i=1; ians) return false;
    for(int len=1; len

发表评论

邮箱地址不会被公开。 必填项已用*标注