bzoj 2824: [AHOI2012]铁盘整理

.

题意：一个序列，每次可以翻转前面一段，求最少多少次可以把序列从小到大排好序。
题解：
一开始看错题。。想了好久。。。
搜索+剪枝。1.步数的上限是(n-1)*2。怎么理解呢？我们先把最大的翻转到最前面，再整个翻转使它调到最后面；再把第二大的翻转到最前面，再调到倒数第二位。这样下去，每一个数最多也只用操作两次，最小的那个已经不用动了。
2.有一个估价函数。从当前状态到目标状态最少也要【现在相邻而目标不相邻的个数】步。一次翻转最多只能消除一对【现在相邻而目标不相邻】。
代码：慢到飞起。。已经被status踢出去了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,ans;
struct hh
{
    int a,pos,id;
}a[60];

int cmp1(hh x,hh y)
{
    return x.a<y.a;
}
int cmp2(hh x,hh y)
{
    return x.id<y.id;
}
bool chk()
{
    for(int i=1;i<=n;i++)
    if(a[i].pos!=i)
    return 0;
    return 1;
}
void dfs(int x)
{
    if(x>ans)
    return;
    if(chk())
    {
        ans=min(ans,x);
        return;
    }
    int cnt=0;
    for(int i=1;i<n;i++)
    cnt+=abs(a[i].pos-a[i+1].pos)!=1;
    if(x+cnt<=ans)
    {
        for(int i=2;i<=n;i++)
        {
            reverse(a+1,a+1+i);
            dfs(x+1);
            reverse(a+1,a+1+i);
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].a);
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp1);
    for(int i=1;i<=n;i++)
    a[i].pos=i;
    sort(a+1,a+1+n,cmp2);
    ans=n<<1;
    dfs(0);
    printf("%d",ans);
}