[ICPC2017 WF]F – Posterize

题目链接：https://codeforces.com/gym/101471

题目大意

给定 d 类元素，第 i 类元素的取值为 r_i​，且有 p_i​ 个，按照这些信息可以将这些元素排列在一个长度为 n=\sum p_i​ 的序列里，现在你要做的是规划一个长度为 k 的序列 v_i​，使得按照如下定义的序列误差最小：
\sum\limits_{i=1}^n \min\limits_{1 \le j \le k}(r_i-v_j)^2

求最小序列误差。

1 \le k \le d \le 256,0 \le r \le 255，1 \le p \le 2^{26}

题目数据按照 r_i 的递增顺序输入。

Time limit: 2 s, Memory limit: 512 MB.

Solution

选 k 个数 v_i (i ：1 \to k) ，思考发现有这样一个性质

在最优解中，如果把 r_i 序列按照与其匹配的 v_j 划分为 k 块，那么 k 块一定在 r 序列中是连续的（ r 有序递增）

如图所示：

那么我们先将任意区间 [l,r] 对应的最有的 v 跑出，装入 F[l,r] 中，然后在进行一次线性 dp，将 r_i 序列划分为 k 段，即可求出答案。

#include<bits/stdc++.h>
#define ll long long
const int N = 257;
int k,d,r[N],p[N];
ll F[N][N],dp[N][N];
int main(){
    scanf("%d%d",&d,&k);
    for(int i=1;i<=d;++i)
        scanf("%d%d",&r[i],&p[i]);
    memset(F,0x3f,sizeof(F));
    for(int v=0;v<=255;++v){
        for(int l=1;l<=d;++l){
            ll sum = 0;
            for(int r=l;r<=d;++r){
                sum+=1ll*(::r[r]-v)*(::r[r]-v)*p[r];
                F[l][r]=std::min(F[l][r],sum);
            }
        }
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int p=1;p<=k;++p){
        for(int i=0;i<=d;++i){
            for(int j=i+1;j<=d;++j){
                dp[j][p]=std::min(dp[j][p],dp[i][p-1]+F[i+1][j]);
            }
        }
    }
    printf("%lld",dp[d][k]);
}