题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6049
题意：一个序列，你可以把一些元素拿出来组成一个小序列，但是要保证小序列是连续的，你确定了小序列之后可以交换一次两个小序列，问你能不能让这个序列变成1-n的序列，并且要你找到最多分成多少个小序列，求最大值。

解法：我的代码，几乎抄了标程的。我再按照我的理解复述一次题解。代码里面的。
//mn[i][j]区间最小
//mx[i][j]区间最大
//f[i][k]记录i,j段最多可分成几个小段
//pre[i]从i开始的上次的可行区间的右端点
如果我们预处理出这些就可以做了。
设要交换的区间为a,b。
一开始先求seg_a的左右端点即i和j，则a必须满足可行，即f[i][j]!=0，同时必须满足，a为最左边的段或者a左边的段包括了(1,i-1)的数字对于每个可行的a，设k为a中的最大值，则
1.如果k==n的话，那么b是最右边的段
2.否则b右边的段为seg(k+1,n),且必须包括(k+1,n)中的所有数
然后枚举b的左端点t使b合法，又必须满足mi[t][k]==i，才能保证a和b交换后整个数列从1~n递增。
做完这道题非常不解，HDU排行榜上的第一页的跑得很快，标程要跑1600ms，难道这题还有更优的做法？

复杂度证明：O（n^2）这题由于n变为了3000，因此需要对两处都进行优化，预处理和暴力枚举的区间都要进行优化。预处理的时候会发现其实有很多无用状态，我们可以用la数组来防止这种现象的发生。这样就做到n^2的了。暴力枚举的时候你需要进行枚举两段就行了。这里有个细节就是你枚举删除的第一段的时候和最后一段留下的是要求连接在一起，因此这样会减去很多种无用情况，复杂度最坏情况只有n^2。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3002;
int T, n, a[maxn], mx[maxn][maxn], mi[maxn][maxn], f[maxn][maxn], pre[maxn], ans;
//mn[i][j]区间最小
//mx[i][j]区间最大
//f[i][k]记录i,j段最多可分成几个小段
//pre[i]从i开始的上次的可行区间的右端点
struct FastIO
{
    static const int S = 1310720;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar()
    {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) return -1;
        return buf[pos ++];
    }
    inline int xuint()
    {
        int c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x;
    }
    inline int xint()
    {
        int s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline void xstring(char *s)
    {
        int c = xchar();
        while (c <= 32) c = xchar();
        for (; c > 32; c = xchar()) * s++ = c;
        *s = 0;
    }
    inline void wchar(int x)
    {
        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos ++] = x;
    }
    inline void wint(int x)
    {
        if (x < 0) wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n ++] = '0' + x % 10, x /= 10;
        while (n--) wchar(s[n]);
        wchar('\n');
    }
    inline void wstring(const char *s)
    {
        while (*s) wchar(*s++);
    }
    ~FastIO()
    {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;
void pre_deal()
{
    memset(f, 0, sizeof(f));
    for(int i=1; i<=n; i++){
        pre[i] = i;
        f[i][i] = 1;
        mi[i][i] = mx[i][i] = a[i];
    }
    for(int i=1; i<=n; i++){
        for(int j=i+1; j<=n; j++){
            mx[i][j] = max(mx[i][j-1], a[j]);
            mi[i][j] = min(mi[i][j-1], a[j]);
        }
    }
    for(int len = 2; len <= n; len++){
        for(int st = 1; st+len-1 <= n; st++){
            int en = st+len-1;
            if(mx[st][en]-mi[st][en]+1 != en-st+1){
                f[st][en] = 0;
            }
            else{
                if(mi[st][en] < mi[st][pre[st]]){
                    f[st][en] = 1;
                }
                else{
                    f[st][en] = f[st][pre[st]]+f[pre[st]+1][en];
                }
                pre[st] = en;
            }
        }
    }
}
void work()
{
    ans = max(1, f[1][n]);
    int k;
    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            if(f[i][j]&&(i==1||(f[1][i-1]&&mi[1][j-1]==1))){
                k = mx[i][j];
                if(k==n||(f[k+1][n]&&mx[k+1][n]==n)){
                    for(int t=j+1; t<=k; t++){
                        if(mi[t][k]==i&&f[t][k]){
                            ans = max(ans, f[1][i-1]+1+f[j+1][t-1]+1+f[k+1][n]);
                        }
                    }
                }
            }
        }
    }
}
int main()
{
    T = io.xint();
    while(T--)
    {
        n = io.xint();
        for(int i=1; i<=n; i++) a[i] = io.xint();
        pre_deal();
        work();
        io.wint(ans);
    }
    return 0;
}