JZOJ5441. 【NOIP2017提高A组冲刺11.1】序列

Description

给定一个1~n的排列x，每次你可以将x1~xi翻转。你需要求出将序列变为升序的最小操作次数。有多组数据。

Input

第一行一个整数t表示数据组数。
每组数据第一行一个整数n，第二行n个整数x1~xn。

Output

每组数据输出一行一个整数表示答案。

Sample Input

1
8
8 6 1 3 2 4 5 7

Sample Output

Data Constraint

对于100%的测试数据，t=5，n<=25。
对于测试点1,2，n=5。
对于测试点3,4，n=6。
对于测试点5,6，n=7。
对于测试点7,8,9，n=8。
对于测试点10，n=9。
对于测试点11，n=10。
对于测试点i (12<=i<=25)，n=i。

题解

看到数据范围不是很大，就知道是搜索的题目。
最容易想到双向bfs，
通过哈希判重。
实际上，这个方法的时间复杂度是很优秀的，
关键问题是状态太多了，哈希很容易出错。

迭代加深搜索，
这也是一个很不错的搜索方式，
但是只有迭代加深搜索是不行的，
还要用一个估价函数。
估价函数需要容易求出，而且剪枝有效的。
一个状态变为升序的最小代价，
这个并不是很容易得到。

至少需要的步数，每次翻转只会改变一对相邻数对，因此对于一个状态求出相差>1 的相邻数对的数量，剩余步数一定大于这个值。
这个剪枝还是非常有用的，至少可以ac这题。

code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string.h>
#include <algorithm>
#define ll long long
#define N 1000003
#define M1 1233233
#define M2 12100
#define M3 20011110
using namespace std;
char ch;
void read(int& n)
{
    n=0;
    ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while('0'<=ch && ch<='9')n=(n<<1)+(n<<3)+ch-'0',ch=getchar();
}
void write(int x)
{
if(x>9)write(x/10);
putchar(x%10+48);
}

int T,n,a[30],ans;

int g()
{
int s=0;
for(int i=1;i<=n;i++)
if(abs(a[i]-a[i+1])!=1)s++;
return s;
}

bool pd()
{
for(int i=1;i<=n;i++)
if(a[i]!=i)return 0;
return 1;
}

bool dg(int x)
{
if(x+g()>ans)return 0;
if(pd())return 1;
int t[30];
memcpy(t,a,sizeof(t));
for(int i=2;i<=n;i++)
    {
for(int j=1;j<=i;j++)
            a[j]=t[i-j+1];
for(int j=i+1;j<=n;j++)
            a[j]=t[j];
if(dg(x+1))return 1;
    }
memcpy(a,t,sizeof(a));
return 0;
}

int main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    read(T);
while(T--)
    {
        read(n);
for(int i=1;i<=n;i++)
            read(a[i]);
        a[n+1]=n+1;
for(ans=0;!dg(0);ans++);
        write(ans);putchar('\n');
    }
return 0;
}

秒客网