AcWing 330. 估算

大型补档计划

若 \(K = 1\)，显然，\(B[i]\) 取 \(A\) 序列的中位数时最优。

考虑扩展，我们只需要把 \(A\) 分成 \(K\) 段，每段内， \(B\) 最优的取值即这一段的中位数

设 \(g(l, r)\) 为 \([l, r]\) 这一段 A 数组序列的中位数

设 \(f[i][j]\) 为把前 \(i\) 个数分成 \(j\) 段的最小值。

考虑枚举一个 \(k < i\)

\(f[i][j] = min(f[k][j - 1] + g(k + 1, i))\)

若朴素计算 g，则复杂度 O(N ^ 3K)

从大往小枚举 k。

我们需要一个数据结构支持两个操作：

加入一个数 a[k + 1]
查询集合中所有数与中位数差的绝对值。

这就是动态中位数那道题，可以用对顶堆 / 线段树 / 平衡树，由于对顶堆比较好写就用它了。

然后复杂度就是 \(O(N ^ 2KLogN)\)。但是复杂度还是 \(1e9\) 左右，会暴毙。

考虑 \(g(k + 1, i)\) 不随 j 的变化而变化，所以可以预处理 \(g(k + 1, i)\) （时间复杂度\(O(N^2LogN)\)）

复杂度就是\(O(N ^ 2K) 1e8\) 跑的还是很慌 #只有吸氧才能过哇哇哇

#pragma GCC optimize(2)

#include <cstdio>

#include <iostream>

#include <queue>

#include <vector>

#include <cstring>

#define rint register int

using namespace std;

const int N = 2005, S = 26;

int n, K, a[N], s1, s2, f[N][S], g[N][N];

priority_queue<int> q1; // 大跟堆

priority_queue<int, vector<int>, greater<int> > q2; // 小跟堆

void inline clear() {

    while (q1.size()) q1.pop();

    while (q2.size()) q2.pop();

    s1 = s2 = 0; }

void inline insert(int x) {

	if (q1.empty() || x <= q1.top()) q1.push(x), s1 += x;

	else q2.push(x), s2 += x;

	// 保持 q1.size == q2.size 或者 q1.size == q2.size + 1

	if (q1.size() > q2.size() + 1) {

		s2 += q1.top(), s1 -= q1.top();

		q2.push(q1.top()), q1.pop();

	}  else if (q2.size() > q1.size()) {

		s1 += q2.top(), s2 -= q2.top();

		q1.push(q2.top()), q2.pop();

	}

}

int inline query() {

    int s = 0;

    if (q1.size()) s += q1.top() * q1.size() - s1;

    if (q2.size()) s += s2 - q1.top() * q2.size();

	return s;

}

int main() {

	while (scanf("%d%d", &n, &K), n || K) {

		memset(f, 0x3f, sizeof f);

		for (rint i = 1; i <= n; i++) scanf("%d", a + i);

		for (rint i = 1; i <= n; i++) {

		    clear();

			for (int k = i; k; k--)

				insert(a[k]), g[k][i] = query();

		}

		f[0][0] = 0;

		for (rint i = 1; i <= n; i++) {

		    for (rint j = 1; j <= K; j++)

		        for (rint k = 0; k < i; k++)

		            f[i][j] = min(f[i][j], f[k][j - 1] + g[k + 1][i]);

		}

		printf("%d\n", f[n][K]);

	}

	return 0;

}

巴特西

AcWing 330. 估算

最新文章

热门文章