bzoj 2933 [Poi1999]地图

bzoj 2933 [Poi1999]地图

​​ Description

一个人口统计办公室要绘制一张地图。由于技术的原因只能使用少量的颜色。两个有相同或相近人口的区域在地图应用相同的颜色。例如一种颜色k，则A(k) 是相应的数，则有： 在用颜色k的区域中至少有一半的区域的人口不大于A(k) 在用颜色k的区域中至少有一半的区域的人口不小于A(k) 区域颜色误差是该区域的人口与A(k)差的绝对值。累计误差是所有区域颜色误差的总和。我们要求出一种最佳的染色方案（累计误差最小）。 任务 写一个程序： 读入每个区域的人口数 计算最小的累计误差 将结果输出 Input

第一行有一个整数n，表示区域数，10< n <3000。在第二行中的数m表示颜色数，2 <= m <= 10。在接下来的n中每行有一个非负整数，表示一个区域的人口。人口都不超过2^30。 Output 输出一个整数，表示最小的累计误差 Sample Input 11 3 21 14 6 18 10 2 15 12 3 2 2 Sample Output 15 贪心：排序更优 dp[i][j]表示前i个分成j块的最小代价 预处理trick pre[i][j]表示i~j分一块的代价

#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=3300;ll dp[N][11],pre[N][N];int n,m,a[N];int main(){ freopen("bzoj2933.in","r",stdin); n=read();m=read(); for (int i=1;i<=n;++i) a[i]=read(); sort(a+1,a+n+1); for (int j=1;j<=n;++j) for (int i=j-1;i;--i) pre[i][j]=pre[i+1][j]+a[(i+1)+j>>1]-a[i]; for (int i=0;i<=n;++i) for (int j=0;j<=m;++j) dp[i][j]=1LL<<60; dp[0][0]=0; for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) for (int k=0;k

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。