洛谷P2534/AHOI2012 铁盘整理

@Pelom  November 7, 2019

题意

给出一个数列,一次可以翻转$1 \dots i(i\in[1,n])$的数,求最少操作多少次使得数列单增

数据范围:$1 \le n \le 50,1 \le r \le 100$

题解

先离散化,原数列转化为$1 \dots n$的一个排列
此时进行一次翻转最多只能改变一对相邻数的差,而最终状态即为相邻数的差都为$1$
因此将估价函数定为

inline int eva(){
    int res=0;
    for(int i=1;i<=n;i++)
        res+=abs(a[i]-a[i+1])!=1;
    return res;
}

计算有多少个相邻的数差不为$1$,那么所需最少的步数与之相等
注意将第$n+1$项的值赋为$n+1$,否则可能是反序的(即单减)

注:

  • 该题数据范围$n$比题面给出的要小,而题面给出的数据很难有复杂度正确的程序通过

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=50+10;
int n;
int a[N],b[N];
bool f;
inline int eva(){
    int res=0;
    for(int i=1;i<=n;i++)
        res+=abs(a[i]-a[i+1])!=1;
    return res;
}
void dfs(int s,int d,int p){
    if(f)
        return ;
    int h=eva();
    if(s+h>d)
        return ;
    if(h==0){
        f=1;
        return ;
    }
    for(int i=1;i<=n;i++){
        if(i==p)
            continue;
        reverse(a+1,a+i+1);
        dfs(s+1,d,i);
        reverse(a+1,a+i+1);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+n+1,a[i])-b;
    a[n+1]=n+1;
    for(int i=0;;i++){
        dfs(0,i,0);
        if(f){
            printf("%d",i);
            break;
        }
    }
    return 0;
}

添加新评论