P6934 [ICPC2017 WF]Posterize

P6934 [ICPC2017 WF]Posterize

翻译比题目难。。
转换一下大意：有一些人站在长度为 (256) 的草地上， 现在让你在草地上插 (K) 面旗子， 人会朝着离自己最近的旗子集合， 一个人花费的代价是 ((p_{人} - p_{旗})^{2})， 你可以自由插这些旗子， 使得花费的总和最小， 求这个最小值。

---

工口发生： 边界刚开始设立得有些模糊， 把插一面旗子作为边界后就可以了

---

Solution

发现长度小于等于256， 可以把复杂度拉到 $$O(n^{3})
考虑分段(dp)， 令 (dp[i][j]) 表示 插j个位置，最后一个为i的 只计算前i个位置的 最小代价
强调只计算前i个位置的是因为我们得使得dp无后效性
这样一来转移方程是很好写的， 我们最后统计答案只需要枚举最后一个端点， 把后面没算上的都加上找最小值就行了
具体转移参考代码吧

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
#define LL long long
#define REP(i, x, y) for(LL i = (x);i <= (y);i++)
using namespace std;
LL RD(){
	LL out = 0,flag = 1;char c = getchar();
	while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
	while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
	return flag * out;
	}
const LL maxn = 260;
const LL inf = 1e18;
LL num, K;
LL a[maxn];
LL dp[maxn][maxn];//插j个位置，最后一个为i的 只计算前i个位置的 最小代价
LL w[maxn][maxn];//i和j插位置，i与j之间的像素产生代价总值
void init(){
	num = RD(), K = RD();
	REP(i, 0, 255)REP(j, 2, 255)dp[i][j] = inf;
	REP(i, 1, num){
		LL pos = RD(), n = RD();
		a[pos] = n;
		}
	
	REP(i, 0, 255){
		REP(j, i + 1, 255){
			REP(k, i + 1, j - 1){//计算k处的代价
				if(k - i <= j - k)w[i][j] += (k - i) * (k - i) * a[k];
				else w[i][j] += (j - k) * (j - k) * a[k];
				}
			}
		}
	REP(i, 0, 255){
		REP(j, 0, i - 1){
			dp[i][1] += (i - j) * (i - j) * a[j];
			}
		}
	}

void work(){
	REP(i, 2, K){
		REP(j, 0, 255){
			REP(k, 0, j - 1){
				dp[j][i] = min(dp[j][i], dp[k][i - 1] + w[k][j]);
				}
			}
		}
	LL ans = inf;
	REP(i, 0, 255){
		LL temp = 0;
		REP(j, i + 1, 255){
			temp += (j - i) * (j - i) * a[j];
			}
		ans = min(ans, dp[i][K] + temp);
		}
	printf("%lld
", ans);
	}
int main(){
	init();
	work();
	return 0;
	}