最少逆序对数量+dp

前言：我一直感觉这题不符合最优子结构性，但是细想一下，我们的子结构就是当前我们处理到 i 的时候，是建立在 i - 1 的时候ans是最小的

这一题还用到了前缀和的思路来处理前面比自己大 以及 后面比自己小的数量

题目地址

#include<bits/stdc++.h>
using namespace std;#define int long long
const int N = (int)1e5+10;
int dp[2][N];
int a[N];
int n,k;// 考虑用
signed main(){cin >> n >> k;for(int i=1;i<=n;i++){cin>> a[i];if(a[i]!=-1) dp[1][a[i]]++; // 计算每个数的数量}for(int i=2;i<=k;i++){dp[1][i] += dp[1][i-1];  // 前缀和统计数量}int ans = 0;for(int i=1;i<=n;i++){if(a[i]==-1){// 开始枚举每一种可能int mx = 0x3f3f3f3f,pos;for(int j=1;j<=k;j++){if(dp[1][j-1] + dp[0][j+1] < mx){mx = dp[1][j-1] + dp[0][j+1];pos = j;}}a[i] = pos; // 最优填空}else{for(int j=a[i];j<=k;j++) dp[1][j]--; // 数量减一}// 开始对这个数进行处理for(int j=1;j<=a[i];j++) dp[0][j]++;ans += dp[0][a[i]+1];}cout << ans;system("pause");return 0;
}