题解 | 冒泡排序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
private:
    // 计算区间[l,r]内的逆序对数量
    int countInversions(vector<int>& arr, int l, int r, bool needReverse) {
        vector<int> temp = arr;
        if (needReverse) {
            reverse(temp.begin() + l, temp.begin() + r + 1);
        }
        
        int count = 0;
        for (int i = l; i <= r; i++) {
            for (int j = i + 1; j <= r; j++) {
                if (temp[i] > temp[j]) {
                    count++;
                }
            }
        }
        return count;
    }

public:
    int solve(vector<int>& arr, int k) {
        int n = arr.size();
        vector<vector<int>> dp(n, vector<int>(k + 1, 0));
        
        // 计算dp数组
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                // 不进行新的翻转操作
                dp[i][j] = dp[i-1][j];
                
                // 尝试所有可能的翻转区间[t,i]
                for (int t = 0; t <= i; t++) {
                    int diff = countInversions(arr, t, i, false) - 
                             countInversions(arr, t, i, true);
                    if (diff < 0) diff = 0;
                    
                    int prevValue = (t > 0) ? dp[t-1][j-1] : 0;
                    dp[i][j] = max(dp[i][j], prevValue + diff);
                }
            }
        }
        
        // 计算原数组的总逆序对数
        int totalInversions = countInversions(arr, 0, n-1, false);
        
        // 返回最终结果
        return totalInversions - dp[n-1][k];
    }
};

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    Solution solution;
    cout << solution.solve(arr, k) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        // 计算区间[l,r]内的逆序对数量
        private int countInversions(int[] arr, int l, int r, boolean needReverse) {
            int[] temp = arr.clone();
            if (needReverse) {
                reverse(temp, l, r);
            }
            
            int count = 0;
            for (int i = l; i <= r; i++) {
                for (int j = i + 1; j <= r; j++) {
                    if (temp[i] > temp[j]) {
                        count++;
                    }
                }
            }
            return count;
        }
        
        private void reverse(int[] arr, int l, int r) {
            while (l < r) {
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
                l++;
                r--;
            }
        }
        
        public int solve(int[] arr, int k) {
            int n = arr.length;
            int[][] dp = new int[n][k + 1];
            
            // 计算dp数组
            for (int i = 1; i < n; i++) {
                for (int j = 1; j <= k; j++) {
                    // 不进行新的翻转操作
                    dp[i][j] = dp[i-1][j];
                    
                    // 尝试所有可能的翻转区间[t,i]
                    for (int t = 0; t <= i; t++) {
                        int diff = countInversions(arr, t, i, false) - 
                                 countInversions(arr, t, i, true);
                        if (diff < 0) diff = 0;
                        
                        int prevValue = (t > 0) ? dp[t-1][j-1] : 0;
                        dp[i][j] = Math.max(dp[i][j], prevValue + diff);
                    }
                }
            }
            
            // 计算原数组的总逆序对数
            int totalInversions = countInversions(arr, 0, n-1, false);
            
            // 返回最终结果
            return totalInversions - dp[n-1][k];
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        Solution solution = new Solution();
        System.out.println(solution.solve(arr, k));
        sc.close();
    }
}

class Solution:
    def count_inversions(self, arr, l, r, need_reverse):
        """计算区间[l,r]内的逆序对数量"""
        temp = arr.copy()
        if need_reverse:
            temp[l:r+1] = temp[l:r+1][::-1]
        
        count = 0
        for i in range(l, r + 1):
            for j in range(i + 1, r + 1):
                if temp[i] > temp[j]:
                    count += 1
        return count
    
    def solve(self, arr, k):
        n = len(arr)
        dp = [[0] * (k + 1) for _ in range(n)]
        
        # 计算dp数组
        for i in range(1, n):
            for j in range(1, k + 1):
                # 不进行新的翻转操作
                dp[i][j] = dp[i-1][j]
                
                # 尝试所有可能的翻转区间[t,i]
                for t in range(i + 1):
                    diff = self.count_inversions(arr, t, i, False) - \
                          self.count_inversions(arr, t, i, True)
                    if diff < 0:
                        diff = 0
                    
                    prev_value = dp[t-1][j-1] if t > 0 else 0
                    dp[i][j] = max(dp[i][j], prev_value + diff)
        
        # 计算原数组的总逆序对数
        total_inversions = self.count_inversions(arr, 0, n-1, False)
        
        # 返回最终结果
        return total_inversions - dp[n-1][k]

def main():
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    
    solution = Solution()
    print(solution.solve(arr, k))

if __name__ == "__main__":
    main()