Solution - Partition Game

Link.

做 vjudge 的题有一种美丽的窒息的感觉。

设 \(f_{i, j}\) 表示前 \(i\) 个选 \(j\) 段出来的最小代价，转移 \(f_{i, j} = \min_{0 \leq k < i} \{f_{k, j - 1} + w_{k + 1, i} \}\)，\(w_{k + 1, i}\) 是 \([k + 1, i]\) 这一段的代价，时间复杂度 \(O(n^2k)\)，然后就不会做了 /ll

观察一下 \(f_{i - 1, j} = \min_{0 \leq k < i - 1} \{f_{k, j - 1} + w_{k + 1, i - 1} \}\)，转移到 \(f_{i, j}\) 首先多了一个 \(f_{i - 1, j - 1} + w_{i - 1 + 1, i} = f_{i - 1, j - 1}\)，可以直接 \(O(1)\) 维护。然后把 \(f_{k, j - 1} + w_{k + 1, i - 1}\) 这一坨看成一个下标为 \(k\) 的序列，转移 \(w_{k + 1, i - 1} \to w_{k + 1, i}\) 只需要考虑 \(a_i\) 的贡献，这个只对 \(a_i\) 这个值的位置有影响，其它的没有影响（反正不涉及到这个值，\(first\) 和 \(last\) 不变），那么有影响的部分就是数组中的 \([1, pre_i]\)，其中 \(pre_i\) 表示 \(i\) 前面第一个和 \(a_i\) 相等的下标，因为 \(pre_i\) 之后是没有和 \(a_i\) 相等的值的。对于这个部分，\(last(a_i)\) 从 \(pre_i\) 变成了 \(i\)，增加量是 \(i - pre_i\)。

把上面这一坨抽象一下，就是维护一个区间加和区间查询最小值的玩意，直接线段树维护 \(O(n \log n)\)。

然后 \(f_{i, j}\) 只和 \(f_{i, j - 1}\) 有关，可以缩掉一维，外层循环 \(j\)，每次计算 \(f_i\) 即可。总的时间复杂度 \(O(k n \log n)\)。

一个小细节：线段树序列下标为 \(k\) 对应的是 \(w_{k + 1, i - 1}\)，要和数组下标对应，实际操作的时候操作的下标是 \([0, pre_i - 1]\)。

namespace liuzimingc {
const int N = 35005, M = 105;
#define endl '\n'

int n, k, a[N], dp[N], pre[N], pos[N];
struct segment_tree {
	int l, r, val, tag;
} t[N << 2];

void push_down(int p) {
	if (t[p].tag) {
		t[p << 1].tag += t[p].tag;
		t[p << 1].val += t[p].tag;
		t[p << 1 | 1].tag += t[p].tag;
		t[p << 1 | 1].val += t[p].tag;
		t[p].tag = 0;
	}
}

void push_up(int p) {
	t[p].val = min(t[p << 1].val, t[p << 1 | 1].val);
}

void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r, t[p].tag = 0;
	if (l == r) {
		t[p].val = dp[l];
		return;
	}
	int mid = l + r >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
	push_up(p);
}

void update(int p, int l, int r, int v) {
	if (l <= t[p].l && t[p].r <= r) {
		t[p].val += v;
		t[p].tag += v;
		return;
	}
	push_down(p);
	int mid = t[p].l + t[p].r >> 1;
	if (l <= mid) update(p << 1, l, r, v);
	if (r > mid) update(p << 1 | 1, l, r, v);
	push_up(p);
}

int ask(int p, int l, int r) {
	if (l <= t[p].l && t[p].r <= r) return t[p].val;
	push_down(p);
	int mid = t[p].l + t[p].r >> 1, ans = 0x3f3f3f3f;
	if (l <= mid) ans = min(ans, ask(p << 1, l, r));
	if (r > mid) ans = min(ans, ask(p << 1 | 1, l, r));
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pre[i] = pos[a[i]];
		pos[a[i]] = i;
	}
	memset(dp, 0x3f, sizeof(dp)); // 现在代码中的 dp 数组随机写 dp / f
	dp[0] = 0;
	for (int j = 1; j <= k; j++) {
		build(1, 0, n);
		for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1];
			if (pre[i]) update(1, 0, pre[i] - 1, i - pre[i]);
			dp[i] = ask(1, 0, i - 1);
		}
	}
	cout << dp[n] << endl;
	return 0;
}
} // namespace liuzimingc