自动搬运

查看原文

来自洛谷，原作者为

	xxy_free_ioi ​博观而约取，厚积而薄发 | 最后在线时间: 2025/8/22 17:05

搬运于2025-08-24 22:25:17，当前版本为作者最后更新于2025-04-08 17:56:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解：P6934 [ICPC 2017 WF] Posterize

区间 DP（为啥我总感觉不像）

解法

我们可以直接预处理一个 $f$ 数组，其中 $f_{i, j}$ 表示将区间 $i \sim j$ 全部转化为一种颜色的误差最小值，由于数据很小，直接暴力算即可。再定义一个数组 $g$，其中 $g_{i,j}$ 表示将 $1 \sim i$ 中的颜色转化为 $j$ 种颜色的最小值。那么，转移式就是 $g_{i,j} = \min(g_{i,j}, g_{l, j - 1} + f_{l+1,i})$，其中 $l \le i - 1$。其实就是把它拆成两份，将 $l+1 \sim i$ 转化为一种颜色，剩下的就是 $g_{l, j-1}$。

代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 300;

int n, k;
int r[N], p[N], f[N][N], g[N][N];

signed main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> r[i] >> p[i];
	
	memset(f, 0x3f, sizeof f);
	memset(g, 0x3f, sizeof g);
	g[0][0] = 0;
	
	for (int c = 0; c < 256; c++) 
		for (int i = 1; i <= n; i++) {
			int s = 0;
			for (int j = i; j <= n; j++)
				f[i][j] = min(f[i][j], s += p[j] * (r[j] - c) * (r[j] - c));
		}
	
	for (int i = 1; i <= n; i++)
		for (int j = 1, x = min(i, k); j <= x; j++)
			for (int l = 0; l < i; l++)
				g[i][j] = min(g[i][j], g[l][j - 1] + f[l + 1][i]);
	
	return cout << g[n][k] << '\n', 0;
}