题解：P6934 [ICPC 2017 WF] Posterize
_QWQ__QWQ_
·
·
题解
看到数据范围，可以 O(n^3) 求解，考虑动态规划。
那么使用动态规划四步法：
-
定义状态：定义 dp_{i,cnt} 表示现在在第 i 个整数的位置时选择了一个整数，并且在第 i 个点之前已经选了 cnt 个点的最小平方误差和。
-
确定答案：dp_{i,k} 的最小值
-
状态转移方程：
dp_{i,cnt}=\min_{j=0}^{j=i-1}\{{dp_{j,cnt-1}+\sum_{x=(i+j)/2+1}^{x=255}pos_x\times\{{(x-i)^2-(x-j)^2}\}}\}
其中的 x 是 [l,r]中大于 (l+r)/2 的整数值，pos_x 表示编号为 x 的红色点的像素数量。
-
初始值与边界：
dp_{i,cnt}=\infty
所以分析完了...吗？
这样看的话我们就需要枚举 $i,j,k$，时间高达 $O(n^3)$，之后再枚举一个 $x$ 显然会超时。
所以我们还需要优化，显然只有最后一个 $x$ 进行优化最好。
$$
\sum_{x=(i+j)/2+1}^{x=255}pos_x\times\{{(x-i)^2-(x-j)^2}\}=\sum_{x=(i+j)/2+1}^{x=255}pos_x\times\{{2\times x\times (j-i)+(i^2-j^2)}\}
$$
那我们就可以令大于 $mid$ 的点的红色点的编号为 $x_1$ 到 $x_n$。
后面的答案继续化简：
$$
\sum_{x=(i+j)/2+1}^{x=255}pos_x\times\{{(x-i)^2-(x-j)^2}\}=\sum_{x=(i+j)/2+1}^{x=255}pos_x\times\{{2\times x\times (j-i)+(i^2-j^2)}\}=2\times(j-i)\times \sum_{x=(i+j)/2}^{x=255}pos_x\times x +(i^2-j^2)\sum_{x=(i+j)/2}^{x=255}pos^x
$$
显然的，后面两个求和可以用后缀和维护
所以代码如下：
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int maxn=5e2+5,mod=1e9+7,inf=1e18;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
int fpow(int a,int b,int p){if(b==0){return 1;}int res=fpow(a,b/2,p)%p;if(b%2==1){return((res*res)%p*a)%p;}else{return(res*res)%p;}}
int n,k;
int dp[maxn][maxn];
int pos[maxn],ans=inf;
int sum[maxn],sum_x[maxn];
signed main(){
cin>>n>>k;
memset(dp,0x3f3f3f3f,sizeof(dp));
for(int i=0;i<=255;i++){
dp[i][1]=0;
}
for(int i=1;i<=n;i++){
int x,c;
cin>>x>>c;
pos[x]+=c;
for(int j=0;j<=255;j++){
dp[j][1]+=(x-j)*(x-j)*c;
}
}
for(int i=255;i>=0;i--){
sum[i]=sum[i+1]+pos[i];
sum_x[i]=sum_x[i+1]+pos[i]*i;
}
for(int i=0;i<=255;i++){
for(int j=0;j<i;j++){
for(int cnt=2;cnt<=k;cnt++){
int mid=(i+j)/2+1;
dp[i][cnt]=min(dp[i][cnt],dp[j][cnt-1]+2*(j-i)*sum_x[mid]+(i*i-j*j)*sum[mid]);
}
}
}
int ans=1e18;
for(int i=0;i<=255;i++){
ans=min(ans,dp[i][k]);
}
cout<<ans<<endl;
return 0;
}
```