60 lines
1.5 KiB
C++
60 lines
1.5 KiB
C++
#include <algorithm>
|
|
#include <cstdio>
|
|
#include <cstring>
|
|
using namespace std;
|
|
typedef long long LL;
|
|
const LL kInf = 0x3f3f3f3f3f3f3f3fll;
|
|
const int kMaxN = 5010;
|
|
int n, k, h[kMaxN], tot_val, t[kMaxN];
|
|
LL cnt[kMaxN], w[kMaxN][kMaxN], dp[kMaxN][2];
|
|
int d[kMaxN][kMaxN];
|
|
void Modify(int p, LL v) {
|
|
for (; p <= tot_val; p += p & (-p)) cnt[p] += v;
|
|
}
|
|
LL Query(int p) {
|
|
LL ret = 0;
|
|
for (; p > 0; p -= p & (-p)) ret += cnt[p];
|
|
return ret;
|
|
}
|
|
int main() {
|
|
#ifdef local
|
|
freopen("pro.in", "r", stdin);
|
|
#endif
|
|
scanf("%d%d", &n, &k);
|
|
// printf("%d %d\n",n,k);
|
|
for (int i = 1; i <= n; i++) {
|
|
scanf("%d", &h[i]);
|
|
t[i] = h[i];
|
|
}
|
|
sort(t + 1, t + 1 + n);
|
|
int pos = 0;
|
|
t[0] = -kInf;
|
|
for (int i = 1; i <= n; i++) {
|
|
if (t[i] != t[pos]) t[++pos] = t[i];
|
|
}
|
|
tot_val = pos;
|
|
for (int i = 1; i <= n; i++) h[i] = lower_bound(t + 1, t + 1 + n, h[i]) - t;
|
|
for (int i = 1; i <= n; i++) {
|
|
Modify(h[i], 1);
|
|
for (int j = i + 1; j <= n; j++) {
|
|
w[i][j] = w[i][j - 1] + j - i - Query(h[j]);
|
|
Modify(h[j], 1);
|
|
}
|
|
memset(cnt, 0, sizeof(cnt));
|
|
}
|
|
memset(dp, 0x3f, sizeof(dp));
|
|
dp[0][0] = 0;
|
|
for (int j = 1; j <= k; j++) {
|
|
d[n + 1][j] = n;
|
|
for (int i = n; i >= j; i--) {
|
|
for (int t = d[i][j - 1]; t <= d[i + 1][j]; t++) {
|
|
if (dp[t][(j - 1) & 1] + w[t + 1][i] < dp[i][j & 1]) {
|
|
dp[i][j & 1] = dp[t][(j - 1) & 1] + w[t + 1][i];
|
|
d[i][j] = t;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
printf("%lld\n", dp[n][k & 1]);
|
|
return 0;
|
|
} |