WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
BZOJ 5449: 序列
BZOJ 5449: 序列

题目链接:5449字符串

题目大意

给定一个长度为n(n\leq 25)的排列P,每次可以翻转P_1\cdots P_x,问至少多少次操作可以令这个排列有序。

题解

第一次做IDA*的题目,其实就是DFS的迭代加深+估价函数。

估价函数设计为当前相邻两个数字绝对值大于1的个数,因为一次翻转最多消除一个这样的位置,所以最终答案肯定大于这个值。

然后枚举迭代次数,使用估价剪枝即可。

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

const int MAXN=50;

int n, num[MAXN];

inline bool check(){
    for (int i=1; i<n; i++) if (num[i]>num[i+1]) return false;
    return true;
}

inline int Abs(int x){ if (x<0) return -x; return x; }
inline int G(){
    int cnt=0;
    for (int i=1; i<n; i++)
        if (Abs(num[i]-num[i+1])>1) cnt++;
    return cnt;
}

bool flag; int mxDepth;
void dfs(int ans, int last){
    if (flag) return;
    if (ans==mxDepth){ if (check()) flag=true; return; }
    if (ans+G()>mxDepth) return;
    for (int i=1; i<=n; i++){
        if (i!=last){
            reverse(num+1, num+i+1);
            dfs(ans+1, i);
            reverse(num+1, num+i+1);
        }
    }
}


inline void solve(int T){
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d", &num[i]);

    flag=false;
    for (mxDepth=0; mxDepth<=30; mxDepth++){
        dfs(0, 0);
        if (flag) { printf("%d\n", mxDepth); return; }
    }
    printf("No\n");
}

int main(){
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

发表评论

textsms
account_circle
email

WNJXYKのBlog

BZOJ 5449: 序列
题目链接:5449字符串 题目大意 给定一个长度为$n(n\leq 25)$的排列$P$,每次可以翻转$P_1\cdots P_x$,问至少多少次操作可以令这个排列有序。 题解 第一次做IDA*的题目,其实就是DFS…
扫描二维码继续阅读
2018-11-27
<--! http2https -->