[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]);
}
0 条评论