专栏文章

题解：P6934 [ICPC 2017 WF] Posterize

__QWQ__QWQ_
P6934题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mingy7a0
此快照首次捕获于
2025/12/02 02:14
3 个月前
此快照最后确认于
2025/12/02 02:14
3 个月前
查看原文
看到数据范围，可以 O(n3)O(n^3) 求解，考虑动态规划。
那么使用动态规划四步法：
  • 定义状态：定义 dpi,cntdp_{i,cnt} 表示现在在第 ii 个整数的位置时选择了一个整数，并且在第 ii 个点之前已经选了 cntcnt 个点的最小平方误差和。
  • 确定答案：dpi,kdp_{i,k} 的最小值
  • 状态转移方程：
    dpi,cnt=min⁡j=0j=i−1{dpj,cnt−1+∑x=(i+j)/2+1x=255posx×{(x−i)2−(x−j)2}} 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}\}}\}
    其中的 xx 是 [l,r][l,r]中大于 (l+r)/2(l+r)/2 的整数值，posxpos_x 表示编号为 xx 的红色点的像素数量。
  • 初始值与边界：
    dpi,cnt=∞dp_{i,cnt}=\infty
dpi,1dp_{i,1} 为所有点到 ii 点的贡献和
所以分析完了...吗？
这样看的话我们就需要枚举 i,j,ki,j,k，时间高达 O(n3)O(n^3)，之后再枚举一个 xx 显然会超时。
所以我们还需要优化，显然只有最后一个 xx 进行优化最好。
∑x=(i+j)/2+1x=255posx×{(x−i)2−(x−j)2}=∑x=(i+j)/2+1x=255posx×{2×x×(j−i)+(i2−j2)}\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)}\}
那我们就可以令大于 midmid 的点的红色点的编号为 x1x_1 到 xnx_n。
后面的答案继续化简：
∑x=(i+j)/2+1x=255posx×{(x−i)2−(x−j)2}=∑x=(i+j)/2+1x=255posx×{2×x×(j−i)+(i2−j2)}=2×(j−i)×∑x=(i+j)/2x=255posx×x+(i2−j2)∑x=(i+j)/2x=255posx\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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...