P2534 [AHOI2012]铁盘整理

题意：一个序列，每次选择一个前缀反转，要使得从小到大排序，问最少反转几次 ------------ $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; } ```