首先定义 wi,j 表示 i∼j 的顺序对个数,设 fi,j 表示当前已经考虑到第 i 个任务,将他们分成 j 段的最小顺序对数量之和,易得转移方程 :
fi,j=k<imin{fk,j−1+wk+1,i}
对于任意 a⩽b⩽c⩽d,使用容斥易证 wa,c+wb,d−wb,c⩽wa,d,故 w 满足四边形不不等式。进一步的,f 的转移满足决策单调性。
有了决策单调性,我们就可以分治转移,同时令人惊喜的是,转移时需要遍历一段连续的区间并计算每一个位置的贡献,于是用 BIT 维护一下就好了。
时间复杂度 Θ(nklog2n).
#include<bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define dep(i, r, l) for (int i = r; i >= l; i--)
const int N = 3e4, K = 30;
int n, k, a[N], dp[K][N], cnt;
namespace BIT {
#define lowbit(x) (x & (-x))
int bit[N], del[N], tot;
void Add (int pos) {
del[++tot] = pos;
for (; pos <= n; pos += lowbit(pos)) bit[pos]++;
}
int Query (int pos) {
int sum = 0;
for (; pos >= 1; pos -= lowbit(pos)) sum += bit[pos];
return sum;
}
void Clear () {
rep(id, 1, tot)
for (int i = del[id]; i <= n; i += lowbit(i)) bit[i]--;
tot = 0;
}
}
using namespace BIT;
void DP (int *f, int *g, int l, int r, int x, int y) {
if (l == r) {
Clear(), cnt = 0;
dep(i, l, x) {
f[l] = min(f[l], g[i] + cnt);
if (i) cnt += Query(a[i]), Add(a[i]);
}
return;
}
int mid = (l + r) >> 1, p;
Clear(), cnt = 0;
dep(i, mid, x) {
if (f[mid] > g[i] + cnt)
f[mid] = g[i] + cnt, p = i;
if (i) cnt += Query(a[i]), Add(a[i]);
}
if (l < mid) DP(f, g, l, mid - 1, x, p);
if (r > mid) DP(f, g, mid + 1, r, p, y);
}
int main () {
scanf("%d%d", &n, &k);
rep(i, 1, n) scanf("%d", &a[i]);
memset(dp, 0x3f, sizeof dp), dp[1][0] = 0;
rep(i, 1, n) dp[1][i] = dp[1][i - 1] + Query(a[i]), Add(a[i]);
rep(i, 1, n) a[i] = n - a[i] + 1;
rep(i, 2, k) DP(dp[i], dp[i - 1], 1, n, 0, n - 1);
printf("%d\n", dp[k][n]);
return 0;
}