SSL2836 2017年11月4日提高组T2 序列（迭代dfs）

2017年11月4日提高组T2 序列

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

7
Hint

【数据规模和约定】
对于100%的测试数据，t=5，n<=25。
对于测试点1，n=5。
对于测试点2，n=6。
对于测试点3，n=7。
对于测试点4，n=8。
对于测试点5，n=10。
对于测试点6，n=12。
对于测试点7，n=16。
对于测试点8，n=18。
对于测试点9，n=22。
对于测试点10，n=25。

分析：每次将 n 翻转到 x1 再翻转到 xn，可以得到一个不超过2n-2 步的做法。由于步数不多，我们可以使用迭代加深搜索。 我们发现每次翻转只会改变一对相邻数对，因此对于一个状态求出相差>1 的相邻数对的数量，剩余步数一定大于这个值。加上这个剪枝就能通过本题。

代码

#include <cstdio>
#define N 30
using namespace std;

int a[N],ans,n,o;
bool fl;

void swap(int x)
{
    int i=1;
    while (i<x)
    {
        a[0]=a[i];
        a[i]=a[x];
        a[x]=a[0];
        i++;
        x--;
    }
}

int absx(int x)
{
    return x>0?x:-x;
}

void dfs(int s,int sum)
{
    if (fl) return;
    if (sum>o) return;
    while (a[s]==s&&s>0) s--;
    if (s==0)
    {
        fl=true;
        return;
    }
    int k=0;
    for (int i=2;i<=s+1;i++)
        if (absx(a[i]-a[i-1])!=1) k++;
    if (sum+k>o) return;
    for (int i=2;i<=s;i++)
    {
        swap(i);
        dfs(s,sum+1);
        swap(i);
    }
}

int main()
{
// freopen("sequence.in","r",stdin);
// freopen("sequence.out","w",stdout);
    int T;
    scanf("%d",&T);
    while (T--)
    {
        ans=123;
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        int x=n;
        while (a[x]==x&&x>0) x--;
        for (int i=0;i<=1234567;i++)
        {
            fl=false;
            o=i;
            dfs(x,0);
            if (fl)
            {
                ans=i;
                break;
            }
        }
        printf("%d\n",ans);
    }
    fclose(stdin);
    fclose(stdout);
}