思路：

分治优化决策单调性dp

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
    
     using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
     
      #define pli pair
      
       #define pii pair
       
        #define piii pair
        
         #define pdd pair
         
          #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 4e4 + 10;const int INF = 0x3f3f3f3f;int dp[N][11], s[N][11], a[N], bit[N], n, k, tot, l, r;inline void add(int x, int a) { while(x <= n) bit[x] += a, x += x&-x;}inline int sum(int x) { int ans = 0; while(x) ans += bit[x], x -= x&-x; return ans;}inline void move(int L, int R) { while(l < L) add(a[l++], -1), tot -= sum(a[l-1]-1); while(l > L) add(a[--l], 1), tot += sum(a[l]-1); while(r < R) add(a[++r], 1), tot += r-l+1-sum(a[r]); while(r > R) add(a[r--], -1), tot -= r-l+1-sum(a[r+1]);}void solve(int L, int R, int l, int r, int k) { if(L > R) return ; int mid = L+R >> 1, up = min(mid-1, r), id = up; dp[mid][k] = INF; for (int i = up; i >= l; --i) { move(i+1, mid); if(dp[i][k-1] + tot < dp[mid][k]) { dp[mid][k] = dp[i][k-1] + tot; id = i; } } solve(L, mid-1, l, id, k); solve(mid+1, R, id, r, k);}int main() { scanf("%d %d", &n, &k); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); for (int i = 1; i <= n; ++i) dp[i][0] = INF; l = 1, r = 0; for (int i = 1; i <= k; ++i) solve(1, n, 0, n-1, i); printf("%d\n", dp[n][k]); return 0;}