P2534 [AHOI2012]铁盘整理 A star
传送门
数据范围较小，考虑dfs
先离散化一波，转化为数的大小关系
最终状态：对于任意的1≤i≤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
82
|
#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;
}
}
}
|
