请问这个做法为什么复杂度假了啊？

思路

\quad

首先定义

w_{i,j}

表示

i\sim j

的顺序对个数，设

f_{i,j}

表示当前已经考虑到第

i

个任务，将他们分成

j

段的最小顺序对数量之和，易得转移方程：

f_{i,j}=\min\limits_{k<i}\{f_{k,j-1}+w_{k+1,i}\}

\quad

对于任意

a\leqslant b\leqslant c\leqslant d

，使用容斥易证

w_{a,c}+w_{b,d}-w_{b,c}\leqslant w_{a,d}

，故

w

满足四边形不不等式。进一步的，

f

的转移满足决策单调性。

\quad

有了决策单调性，我们就可以分治转移，同时令人惊喜的是，转移时需要遍历一段连续的区间并计算每一个位置的贡献，于是用

\rm BIT

维护一下就好了。

\quad

时间复杂度

\Theta(nk\log^2n).

代码

CPP

#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;
}

请问这个做法为什么复杂度假了啊？

讨论操作

思路

代码

评测记录

回复

相关推荐

请问这个做法为什么复杂度假了啊？