P2534 [AHOI2012]铁盘整理

2018-09-13 16:24:32


题意:一个序列,每次选择一个前缀反转,要使得从小到大排序,问最少反转几次


$n<=50,a[i]<=100$ ,这个范围应该是一个搜索题

直接爆搜能得到 $40-60$ 分

可以用 $IDA*$ 来剪枝

可以发现 $ans$ 的上界是 $2(n-1)$

用一个变量 $tot$ 来表示当前序列中应该相邻但并不相邻的数的个数

如果当前操作次数加上 $tot$ 大于 $ans$ 就直接 $return$

如果 $tot$ 为 $0$ 且 $a[1]==1$ ,就更新答案

然后照常 $dfs$ 就好了

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N=55;
int n,a[N],num[N<<1],ans,tot;
void dfs(int sum)
{
    if (sum+tot>=ans) return;
    if (!tot&&a[1]==1) {ans=min(ans,sum); return;}
    for (int i=2;i<=n;i++)
    {
        if (i!=n) tot+=(abs(a[i+1]-a[1])!=1)-(abs(a[i+1]-a[i])!=1);
        for (int j=1;2*j<=i;j++) swap(a[j],a[i-j+1]);
        dfs(sum+1);
        for (int j=1;2*j<=i;j++) swap(a[j],a[i-j+1]);
        if (i!=n) tot-=(abs(a[i+1]-a[1])!=1)-(abs(a[i+1]-a[i])!=1);
    }
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),++num[a[i]];
    for (int i=1;i<=100;i++) num[i]+=num[i-1];
    for (int i=1;i<=n;i++) a[i]=num[a[i]]; ans=2*n-2;
    for (int i=2;i<=n;i++) if (abs(a[i]-a[i-1])!=1) ++tot;
    dfs(0); printf("%d\n",ans);
    return 0;
}