NOIP模拟赛 序列（sequence）
题目描述
给定一个 x 1 , x 2 , … , x n x_1,x_2,\dots,x_n x1,x2,…,xn的序列，每次你可以将 x 1 , x 2 … , x i x_1,x_2\dots,x_i x1,x2…,xi翻转，请求出将序列变为升序的最小操作次数。有多组数据。
输入格式
第一行一个整数 t t t表示数据组数。
每组数据一行一个整数 n n n，第二行 n n n个整数 x 1 , x 2 , … , x n x_1,x_2,\dots,x_n x1,x2,…,xn。
输出格式
每组数据输出一行一个整数表示答案。
样例输入
1
8
8 6 1 3 2 4 5 7
样例输出
7
数据范围
1 ≤ t ≤ 5 , 1 ≤ n ≤ 25 1\leq t\leq 5,1\leq n\leq 25 1≤t≤5,1≤n≤25
题解
每次将最大的没有归位的数翻转到最前面，然后再将其翻转到对应的位置，这样做的操作次数不会超过 2 n − 2 2n-2 2n−2。我们只需要找到操作次数小于 2 n − 2 2n-2 2n−2的做法。因为操作次数不多，所以我们可以用迭代加深搜索。
当然，还需要一些剪枝。我们发现每次翻转最多只会改变一对相邻数对，因此对于每个状态，求出其相差大于 1 1 1的相邻数对的数量，如果剩余步数小于这个值，则这种状态不可行。加上这个剪枝就能过。
code
#include<bits/stdc++.h>
using namespace std;
int T,n,fl,ans,a[35];
void dfs(int t,int now){
if(now>ans) return;
while(t>0&&a[t]==t) --t;
if(t==0){
fl=1;return;
}
int v=0;
for(int i=1;i<n;i++){
if(abs(a[i+1]-a[i])>1) ++v;
}
if(now+v>ans) return;
for(int i=2;i<=t;i++){
reverse(a+1,a+i+1);
dfs(t,now+1);
reverse(a+1,a+i+1);
if(fl) return;
}
}
int main()
{
scanf("%d",&T);
while(T--){
fl=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(ans=0;ans<=2*n-2;ans++){
dfs(n,0);
if(fl) break;
}
printf("%d\n",ans);
}
return 0;
}