hdu6049

题意

给出一串由 \([1, n]\) 组成的 \(n\) 个数，每个数字都不相同。现在要尽可能的分成多个块，每个块内的数可以任意排序，且分完块后可以交换两个块的位置，问使得最后序列有序可以最多分成几个块。

分析

首先暴力预处理出 \(f[i][j]\) 表示区间 \([i, j]\) 最多可以分成多少块（只有某一段区间的所有数字重排后连续才能当做一块，这个可以通过预处理出区间最大值、最小值去判断，而要想形成多个块，必须保证最小值不能改变，一定是第一个块的最小值）。( \(O(n^2)\) ）

然后枚举 \([i, j]\) 也就是我们要交换的第一个块，判断合法性以及后面是否存在一个可以交换的块。（ \(O(n^3)\) 其实几乎是 \(O(n^2)\) ，很多都是无效状态 ）

code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int MAXN = 3e3 + 10;

int n;

int mx[MAXN][MAXN], mn[MAXN][MAXN];

int a[MAXN], f[MAXN][MAXN]; // f[i][j] : [i, j] 最多能分成多少块

void init() {

    for(int i = 1; i <= n; i++) {

        mx[i][i] = mn[i][i] = a[i];

        for(int j = i + 1; j <= n; j++) {

            mx[i][j] = max(mx[i][j - 1], a[j]);

            mn[i][j] = min(mn[i][j - 1], a[j]);

        }

    }

    for(int i = 1; i <= n; i++) {

        int cnt = 1;

        f[i][i] = 1;

        for(int j = i + 1; j <= n; j++) {

            if(mn[i][j - 1] != mn[i][j]) cnt = 0;

            if(j - i == mx[i][j] - mn[i][j]) f[i][j] = ++cnt;

        }

    }

}

int main() {

    int T;

    scanf("%d", &T);

    while(T--) {

        memset(f, 0, sizeof f);

        scanf("%d", &n);

        for(int i = 1; i <= n; i++) {

            scanf("%d", &a[i]);

        }

        init();

        int ans = f[1][n];

        for(int i = 1; i <= n; i++) { // 枚举要交换的左端 [i, j]，判断合法并寻找交换的右端

            for(int j = i; j <= n; j++) {

                if(f[i][j]) {

                    if(i == 1 || (mn[1][i - 1] == 1 && mx[1][i - 1] - mn[1][i - 1] == i - 2)) {

                        int x = mx[i][j];

                        if(x == n || (mx[x + 1][n] == n && mx[x + 1][n] - mn[x + 1][n] == n - x - 1)) {

                            for(int k = x; k > j; k--) {

                                if(f[k][x] && mn[k][x] == i) {

                                    ans = max(ans, f[1][i - 1] + 1 + f[j + 1][k - 1] + 1 + f[x + 1][n]);

                                }

                            }

                        }

                    }

                }

            }

        }

        printf("%d\n", ans);

    }

    return 0;

}