题解 | #冒泡排序#

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int N = 51;
//dp[i][k] 表示数组a[0,i] 执行了不超过k次特定操作后 最大减少的逆序数对 的数量。 答案= a[0,n-1]总逆序数对个数 - dp[n-1][k]
int dp[N][N];
int n,k;
vector<int> a(N, 0);
// 求数组t 在范围[l,r]上的逆序数对 个数
int getCnt(vector<int> t, int l, int r, bool isReverse){
    int res = 0;
    if(isReverse){
        reverse(t.begin()+l, t.begin()+r+1);
    }
    for(int i = l; i <= r; i++){
        for(int j = i + 1; j <= r; j++){
            if(t[i]>t[j]) res++;
        }
    }
    return res;
}
int main() {
    int n,k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    for(int i = 1; i < n; i++){
        for(int k_ = 1; k_ <= k; k_++){
            int tmp = -1;
            //枚举范围[t,i]
            for(int t = 0; t < i; t++){
                //不翻转 和 翻转的 逆序数对的差距
                int d = getCnt(a, t, i, false) - getCnt(a, t, i, true);
                if(d < 0) d = 0;
                tmp = max(tmp, dp[t-1][k_-1]+d);
            }
            // tmp是数组每个范围上，特定操作不超过k的 最大逆序数对 减少数
            dp[i][k_] = max(dp[i-1][k_], tmp);
        }
    }
    cout << getCnt(a, 0,n-1, false) - dp[n-1][k] << endl;
    return 0;

}
// 64 位输出请用 printf("%lld")