Steven_MengのBlog

传送门
数据范围较小,考虑$dfs$

先离散化一波,转化为数的大小关系
最终状态:对于任意的$1 \le i \le n$,$abs(a[i+1]-a[i])==1$ (定义$a[n+1]=n+1$)
考虑一次翻转,翻转$j$大小的区间,每个块里面$abs(a[i+1]-a[i])$不会变,只有$abs(a[j+1]-a[j])$会变。
所以每次操作只能改变一个$abs(a[i+1]-a[i])$
考虑最终状态和现在状态$abs(a[i+1]-a[i])$的不同之处,估价函数就出来了

1
2
3
4
5
6
7
inline int h(){
int cnt=0;
for (register int i=1;i<=n;++i){
cnt+=(int)(Abs(a[i]-a[i+1])!=1);
}
return cnt;
}

然后迭代加深搜索一遍,就能$A$了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define MAXN 55
using namespace std;
inline int read() {
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9') {
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9') {
x=(x*10)+(ch-'0');
ch=getchar();
}
return x*f;
}
int a[MAXN],b[MAXN];
inline void discrete(int n){
for (register int i=1;i<=n;++i){
b[i]=a[i];
}
sort(b+1,b+1+n);
for (register int i=1;i<=n;++i){
a[i]=lower_bound(b+1,b+1+n,a[i])-b;
}
}
inline void Swap(int l,int r){
for (register int i=l,j=r;i<=j;i++,j--){
swap(a[i],a[j]);
}
}
inline int Abs(int i){
return i>0?i:-i;
}
int ans,n,maxdep;
inline int h(){
int cnt=0;
for (register int i=1;i<=n;++i){
cnt+=(int)(Abs(a[i]-a[i+1])!=1);
}
return cnt;
}
bool flag;
void dfs(int nowdep,int last){
if (flag){
return ;
}
int ans=h();
if (nowdep+ans>maxdep) {
return ;
}
if (ans==0){
flag=true;
return ;
}
for (register int i=1;i<=n;++i){
if (i!=last){
Swap(1,i);
dfs(nowdep+1,i);
Swap(1,i);
}
}
}
int main(){
n=read();
for (register int i=1;i<=n;++i){
a[i]=read();
}
discrete(n);
a[n+1]=n+1;
for (register int dep=0;;++dep){
flag=false;
maxdep=dep;
dfs(0,0);
if (flag){
printf("%d\n",dep);
return 0;
}
}
}

 评论