Subtask 1:

Vì mỗi vị trí có hai trường hợp: chọn hoặc không chọn, nên ta có thể quay lui tất cả ~2^n~ cách chọn. Với mỗi trường hợp ta có thể dùng hai con trỏ để tạo dãy sau khi reverse và tính số nghịch thế trong ~O(n^2 / 2)~.

Độ phức tạp: ~O(2^n \cdot n^2 / 2)~.

Subtask 2:

Gọi ~cost[i][j]~ là số nghịch thế tăng lên sau khi đổi chỗ ~a_i~ với ~a_j~ trong dãy hoán vị ban đầu.

Ta có thể dễ dàng tính mảng trên trong độ phức tạp ~O(n^4)~.

Nhận xét 1: Xét trường hợp đổi chỗ cặp phần tử ~a_i~ và ~a_j~ (~i < j~), chỉ những phần tử trong khoảng ~[i, j]~ mới làm thay đổi số nghịch thế, cụ thể:

• Với ~a_i~: ~cost[i][j]~ += ~\sum\limits_{k=i}^{j} (a_k > a_i) - (a_k < a_i)~.
• Với ~a_j~: ~cost[i][j]~ += ~\sum\limits_{k=i}^{j} (a_k < a_j) - (a_k > a_j)~.

Nhận xét 2: Với cách chọn dãy con ~a_{i_1}, a_{i_2}, \cdots, a_{i_{k - 1}}, a_{i_k}~ (~i_1 < i_2 < \cdots < i_k~), việc reverse chính là ta đang thực hiện đổi chỗ lần lượt các cặp phần tử đối xứng ~(i_1, i_k)~, ~(i_2, i_{k - 1})~,... theo thứ tự từ ngoài vào trong. Chính vì cặp phần tử ngoài chứa tất cả các cặp phần tử trong nên chúng độc lập với nhau. Cụ thể hơn, ví dụ ta xét đổi chỗ cặp phần tử (~i_1, i_k~), việc đổi chỗ các cặp phần tử (~i_2, i_{k - 1}~), (~i_3, i_{k - 2}~),... không làm thay đổi ~cost[i_1][i_k]~.

Gọi ~dp[i][j]~ là số nghịch thế nhỏ nhất sau khi xét xong các phần tử từ ~1 \to i~ và từ ~j \to n~.

dp[i][j] = min(dp[i][j], dp[i - 1][j]); /// Không chọn phần tử i
dp[i][j] = min(dp[i][j], dp[i][j + 1]); /// Không chọn phần tử j
dp[i][j] = min(dp[i][j], dp[i - 1][j + 1] + cost[i][j]); /// Chọn cặp phần tử i, j

Độ phức tạp: ~O(n^4)~.

Subtask 3:

Nhận thấy ~cost[i][j]~ được tính từ hai phần: Số nghịch thế tăng lên với ~a_i~ và số nghịch thế tăng lên với ~a_j~. Nên ta sử dụng hai con trỏ để tính mảng ~cost[i][j]~ trong độ phức tạp ~O(n^2)~ như sau:

• Với mỗi ~i~ (~1 \le i \le n~), lần lượt duyệt qua ~j~ (từ ~i \to n~) để tính số nghịch thế tăng lên với ~a_i~ cho ~cost[i][j]~.
• Với mỗi ~j~ (~1 \le j \le n~), lần lượt duyệt qua ~i~ (từ ~j \to 1~) để tính số nghịch thế tăng lên với ~a_j~ cho ~cost[i][j]~.

Độ phức tạp: ~O(n^2)~.

Code mẫu

#include <bits/stdc++.h>
#define VanLoi ""
#define gb(i, j) ((i >> j) & 1)

using namespace std;

const int N = (int)5000 + 5, MOD = (int)1e9 + 7, mod = (int)1e9 + 20041203;

int n, a[N], cost[N][N], dp[N][N], res, bit[N];

void ud(int x) {
    while (x <= n) {
        bit[x]++;
        x += (x & -x);
    }
}

int get(int x) {
    int ans = 0;
    while (x) {
        ans += bit[x];
        x -= (x & -x);
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = n; i >= 1; i--) {
        res += get(a[i]);
        ud(a[i]);
    }
    for (int l = 1; l <= n; l++) {
        int sum = 0;
        for (int r = l + 1; r <= n; r++) {
            cost[l][r] += sum;
            if (a[r] < a[l]) sum--; else sum++;
        }
    }
    for (int r = n; r >= 1; r--) {
        int sum = 0;
        for (int l = r - 1; l >= 1; l--) {
            if (a[r] < a[l]) sum--; else sum++;
            cost[l][r] += sum;
        }
    }
    // f[i][j]: la min khi da xet xong 1 -> i va j -> n
    for (int i = 0; i <= n + 1; i++)
        for (int j = i; j <= n + 1; j++) dp[i][j] = 1e9;
    dp[0][n + 1] = 0;
    for (int i = 0; i <= n; i++)
        for (int j = n + 1; j >= 1; j--) if (dp[i][j] != 1e9) {
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
            dp[i][j - 1] = min(dp[i][j - 1], dp[i][j]);
            dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j] + cost[i + 1][j - 1]);
        }
    int mi = 1e9;
    for (int i = 1; i <= n; i++) {
        mi = min(mi, dp[i][i]);
        if (i < n) mi = min(mi, dp[i][i + 1]);
    }
    cout << res + mi;
}