Problem Description
Sdjpx is a powful man,he controls a big country.There are n soldiers numbered 1~n(1<=n<=3000).But there is a big problem for him.He wants soldiers sorted in increasing order.He find a way to sort,but there three rules to obey.
1.He can divides soldiers into K disjoint non-empty subarrays.
2.He can sort a subarray many times untill a subarray is sorted in increasing order.
3.He can choose just two subarrays and change thier positions between themselves.
Consider A = [1 5 4 3 2] and P = 2. A possible soldiers into K = 4 disjoint subarrays is:A1 = [1],A2 = [5],A3 = [4],A4 = [3 2],After Sorting Each Subarray:A1 = [1],A2 = [5],A3 = [4],A4 = [2 3],After swapping A4 and A2:A1 = [1],A2 = [2 3],A3 = [4],A4 = [5].
But he wants to know for a fixed permutation ,what is the the maximum number of K?
Notice: every soldier has a distinct number from 1~n.There are no more than 10 cases in the input.
1.He can divides soldiers into K disjoint non-empty subarrays.
2.He can sort a subarray many times untill a subarray is sorted in increasing order.
3.He can choose just two subarrays and change thier positions between themselves.
Consider A = [1 5 4 3 2] and P = 2. A possible soldiers into K = 4 disjoint subarrays is:A1 = [1],A2 = [5],A3 = [4],A4 = [3 2],After Sorting Each Subarray:A1 = [1],A2 = [5],A3 = [4],A4 = [2 3],After swapping A4 and A2:A1 = [1],A2 = [2 3],A3 = [4],A4 = [5].
But he wants to know for a fixed permutation ,what is the the maximum number of K?
Notice: every soldier has a distinct number from 1~n.There are no more than 10 cases in the input.
Input
First line is the number of cases.
For every case:
Next line is n.
Next line is the number for the n soildiers.
For every case:
Next line is n.
Next line is the number for the n soildiers.
Output
the maximum number of K.
Every case a line.
Every case a line.
Sample Input
2
5
1 5 4 3 2
5
4 5 1 2 3
Sample Output
4
2
Hint
Test1: Same as walk through in the statement. Test2: [4 5] [1 2 3] Swap the 2 blocks: [1 2 3] [4 5].
启发博客：http://www.cnblogs.com/FxxL/p/7253028.html
题意： 给出n，一个1~n的排列，要求进行三步操作
1.分区（随便分）
2.对分好的每一个区内进行从小到大的排序
3.挑选两个区进行交换（只能挑选两个，只能交换易次），使得序列的顺序变成1-n;
问在满足要求的情况下，最多能分成多少区
题解：第一步是分区，第二步是枚举。
分区是开了一个f[i][j]数组用来记录，i-j区间里可以有多少满足要求的段，用到mx,mi，r来辅助，具体可见代码注释。
枚举是枚举要交换的两个区间，每次更新答案的最大值。设左右区间分别为seg_a,seg_b。
seg_a要满足：第一段或者之前包括1~i-1的所有数字，当然自身不能为空
把这个区间最大的数定义为k，根据k来枚举seg_b，k是seg_b的右端点
还需满足k==n或者k+1及以后的所有数字包含k+1~n
seg_b要满足：k是seg_b的右端点，自身不为空，要保证它的最小值是i
像上述这样来做即可，当然中间会有一些不小心造成的WA点，大家注意即可
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
#define MAXN 3005 int a[MAXN],res,n;
int mi[MAXN][MAXN],mx[MAXN][MAXN];
//mi[i][j]表示从i到j的最小值，mx[i][j]表示从i到j的最大值
int f[MAXN][MAXN],r[MAXN];
//f[i][j]表示从i到j可以分成的区间数，r[i]表示最近一次从i开始的区间的右端（方便更新） void init()//第一步，分块
{
memset(mi,,sizeof(mi));
memset(mx,,sizeof(mx));
memset(f,,sizeof(f));
memset(r,,sizeof(r));
for(int i=;i<=n;i++)
{
mi[i][i]=a[i];
mx[i][i]=a[i];
f[i][i]=;
r[i]=i;
}
//为mi,mx赋值
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
mx[i][j]=max(a[j],mx[i][j-]);
mi[i][j]=min(a[j],mi[i][j-]);
}
//为f数组赋值
for(int t=;t<=n;t++)//t在枚举区间长度
for(int i=;i+t-<=n;i++)
{
int j=i+t-;
//不是连续的一段无法分区间
if(mx[i][j]-mi[i][j]!=t-)
f[i][j]=;
else
{
//j一定大于r[i]
if(mi[i][r[i]]>mi[i][j])
f[i][j]=;
else
f[i][j]=f[i][r[i]]+f[r[i]+][j];
r[i]=j;//这个r数组很精华
}
}
} void solve()//第二步，枚举找交换区间
{
int k;
res=max(,f[][n]);//WA点，一开始写成res=1就WA了
//先枚举seg_a
for(int i=;i<=n;i++)
for(int j=i;j<=n;j++)
{
//满足条件才能继续枚举seg_b
if(i==||(f[][i-]!=&&mi[][i-]==))
{
k=mx[i][j];
if(f[i][j]&&(k==n||(f[k+][n]!=&&mx[k+][n]==n)))
{
for(int t=j+;t<=k;t++)
{
if(f[t][k]&&mi[t][k]==i)
{
//printf("%d %d %d %d %d\n",i,j,t,k,f[1][i-1]+1+f[j+1][t-1]+1+f[k+1][n]);
res=max(res,f[][i-]++f[j+][t-]++f[k+][n]);
}
}
}
}
}
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
init();
solve();
printf("%d\n",res);
}
return ; }