企业官网建设流程全解析

P6934 [ICPC 2017 WF] Posterize题目描述数字图像中的像素可以用三个范围在000到255255255之间的整数表示分别表示红、绿、蓝三种颜色的强度。为了压缩图像或创造艺术效果许多照片编辑工具包括一个posterize操作其工作原理如下。每个颜色通道单独检查这个问题只关注红色通道。对于红色通道posterized 图像最多允许kkk个整数而不是允许从000到255255255的所有整数。每个像素的原始红色强度被替换为允许整数中最接近的一个。照片编辑工具选择一组kkk个整数以最小化原始图像中所有像素引入的平方误差之和。如果有nnn个像素的原始红色值为r1,…,rnr_{1}, \ldots, r_{n}r1​,…,rn​并且有kkk个允许的整数v1,…,vkv_{1}, \ldots, v_{k}v1​,…,vk​则平方误差之和定义为∑i1nmin⁡1≤j≤k(ri−vj)2\sum\limits_{i1}^n \min\limits_{1 \le j \le k}(r_i-v_j)^2i1∑n​1≤j≤kmin​(ri​−vj​)2你的任务是计算在给定参数kkk和图像像素红色强度描述的情况下可以实现的最小平方误差之和。输入格式输入的第一行包含两个整数d(1≤d≤256)d (1 \le d \le 256)d(1≤d≤256)表示原始图像中出现的不同红色值的数量以及k(1≤k≤d)k (1 \le k \le d)k(1≤k≤d)表示 posterized 图像中允许的不同红色值的数量。接下来的ddd行表示图像中具有各种红色值的像素数量。每行包含两个整数r(0≤r≤255)r (0 \le r \le 255)r(0≤r≤255)和p(1≤p≤226)p (1 \le p \le 2^{26})p(1≤p≤226)其中rrr是一个红色强度值ppp是具有红色强度rrr的像素数量。这ddd行按红色值递增的顺序给出。输出格式显示为优化选择的kkk个允许整数值的平方误差之和。输入输出样例 #1输入 #12 1 50 20000 150 10000输出 #166670000输入输出样例 #2输入 #22 2 50 20000 150 10000输出 #20输入输出样例 #3输入 #34 2 0 30000 25 30000 50 30000 255 30000输出 #337500000说明/提示时间限制2 秒内存限制512 MB。题面翻译由 ChatGPT-4o 提供。C实现#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN300;intn,k;intr[N],p[N],f[N][N],g[N][N];signedmain(){cinnk;for(inti1;in;i)cinr[i]p[i];memset(f,0x3f,sizeoff);memset(g,0x3f,sizeofg);g[0][0]0;for(intc0;c256;c)for(inti1;in;i){ints0;for(intji;jn;j)f[i][j]min(f[i][j],sp[j]*(r[j]-c)*(r[j]-c));}for(inti1;in;i)for(intj1,xmin(i,k);jx;j)for(intl0;li;l)g[i][j]min(g[i][j],g[l][j-1]f[l1][i]);returncoutg[n][k]\n,0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容