HDU 6049 17多校2 Sdjpx Is Happy（思维题difficult）

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.

Input

First line is the number of cases.
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.

Sample Input

1 5 4 3 2

4 5 1 2 3

Sample Output

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点，大家注意即可

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 using namespace std;
 6 #define MAXN 3005
 7 
 8 int a[MAXN],res,n;
 9 int mi[MAXN][MAXN],mx[MAXN][MAXN];
10 //mi[i][j]表示从i到j的最小值，mx[i][j]表示从i到j的最大值
11 int f[MAXN][MAXN],r[MAXN];
12 //f[i][j]表示从i到j可以分成的区间数，r[i]表示最近一次从i开始的区间的右端（方便更新）
13 
14 
15 void init()//第一步，分块
16 {
17     memset(mi,0,sizeof(mi));
18     memset(mx,0,sizeof(mx));
19     memset(f,0,sizeof(f));
20     memset(r,0,sizeof(r));
21     for(int i=1;i<=n;i++)
22     {
23         mi[i][i]=a[i];
24         mx[i][i]=a[i];
25         f[i][i]=1;
26         r[i]=i;
27     }
28     //为mi,mx赋值
29     for(int i=1;i<=n;i++)
30     for(int j=i+1;j<=n;j++)
31     {
32         mx[i][j]=max(a[j],mx[i][j-1]);
33         mi[i][j]=min(a[j],mi[i][j-1]);
34     }
35     //为f数组赋值
36     for(int t=2;t<=n;t++)//t在枚举区间长度
37     for(int i=1;i+t-1<=n;i++)
38     {
39         int j=i+t-1;
40         //不是连续的一段无法分区间
41         if(mx[i][j]-mi[i][j]!=t-1)
42             f[i][j]=0;
43         else
44         {
45             //j一定大于r[i]
46             if(mi[i][r[i]]>mi[i][j])
47                 f[i][j]=1;
48             else
49                 f[i][j]=f[i][r[i]]+f[r[i]+1][j];
50             r[i]=j;//这个r数组很精华
51         }
52     }
53 }
54 
55 void solve()//第二步，枚举找交换区间
56 {
57     int k;
58     res=max(1,f[1][n]);//WA点，一开始写成res=1就WA了
59     //先枚举seg_a
60     for(int i=1;i<=n;i++)
61     for(int j=i;j<=n;j++)
62     {
63         //满足条件才能继续枚举seg_b
64         if(i==1||(f[1][i-1]!=0&&mi[1][i-1]==1))
65         {
66             k=mx[i][j];
67             if(f[i][j]&&(k==n||(f[k+1][n]!=0&&mx[k+1][n]==n)))
68             {
69                 for(int t=j+1;t<=k;t++)
70                 {
71                     if(f[t][k]&&mi[t][k]==i)
72                     {
73                         //printf("%d %d %d %d %d
",i,j,t,k,f[1][i-1]+1+f[j+1][t-1]+1+f[k+1][n]);
74                         res=max(res,f[1][i-1]+1+f[j+1][t-1]+1+f[k+1][n]);
75                     }
76                 }
77             }
78         }
79     }
80 }
81 
82 int main()
83 {
84     int T;
85     scanf("%d",&T);
86     while(T--)
87     {
88         scanf("%d",&n);
89         for(int i=1;i<=n;i++)
90             scanf("%d",&a[i]);
91         init();
92         solve();
93         printf("%d
",res);
94     }
95     return 0;
96 
97 }