题解：P6934 [ICPC 2017 WF] Posterize

· · 题解

题解：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;
}