P5929 [POI 1999 R3] 地图题目背景一个人口统计办公室要绘制一张地图。题目描述由于技术的原因只能使用少量的颜色。两个有相同或相近人口的区域在地图应用相同的颜色。例如一种颜色kkk则A(k)A(k)A(k)是相应的数则有在用颜色kkk的区域中至少有一半的区域的人口不大于A(k)A(k)A(k)在用颜色kkk的区域中至少有一半的区域的人口不小于A(k)A(k)A(k)。区域颜色误差是该区域的人口与A(k)A(k)A(k)差的绝对值。累计误差是所有区域颜色误差的总和。我们要求出一种最佳的染色方案使得累计误差最小。输入格式第一行有一个整数nnn表示区域数。在第二行中的数mmm表示颜色数。在接下来的nnn行中每行有一个非负整数表示一个区域的人口。人口都不超过2302^{30}230。输出格式输出一个整数表示最小的累计误差。输入输出样例 #1输入 #111 3 21 14 6 18 10 2 15 12 3 2 2输出 #115说明/提示对于100%100\%100%的数据10n300010 n 300010n30002≤m≤102 \le m \le 102≤m≤10。C实现#includebits/stdc.husingnamespacestd;constintN3005;constintM15;intn,m;intf[N][M],sum[N],a[N];intcolor(intl,intr){intmid(lr)/2;//求中位数的位置returna[mid]*(mid-l)-sum[mid-1]sum[l-1]-a[mid]*(r-mid)sum[r]-sum[mid];//O(1)优化}intmain(){cinnm;for(inti1;in;i){cina[i];}sort(a1,an1);for(inti1;in;i){sum[i]sum[i-1]a[i];//前缀和预处理}memset(f,0x3f,sizeoff);//开始全赋最大值f[0][0]0;for(inti1;in;i){for(intj1;jm;j){for(intk0;ki;k){f[i][j]min(f[i][j],f[k][j-1]color(k1,i));//转移方程}}}coutf[n][m];return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容