BZOJ2933：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

输出一个整数，表示最小的累计误差

Solution

为了使几个区域的人口更加接近，所以先排序，然后考虑怎样将几个区域的人口分为一段，使得误差最小。又因为i号位之前的分法对于之后的分法没有影响，所以果断DP。如果用f[i][j]表示前i个区域分成j段，再去枚举这i个区域最后一段切在哪里(k)，就能得到状态转移方程：f[i][j]=min(f[i][j],f[k][j-1]+(k+1到i号位的误差));

那么就要用前缀和处理出把i到j号位分成一段的误差(1<=i<=j<=n)，可离线读取。s为a的前缀和数组，那么i到j位的误差就是(mid为i到j的中位数)，a[mid]*(mid-i)-(s[mid-1]-s[i-1])+(s[j]-s[mid])-a[mid]*(j-mid)，画数轴自己推一下会好理解得多。

Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int a[];
long long s[],w[][],f[][];
int main()
{
int n,m;
cin>>n>>m;
for (int i=; i<=n; i++)
cin>>a[i];
sort(a+,a+n+);//先排序
for (int i=; i<=n; i++)
s[i]=s[i-]+a[i];//前缀和
int mid;
for (int i=; i<=n; i++)
for (int j=i; j<=n; j++)
{
mid=(i+j)/;
w[i][j]=a[mid]*(mid-i)-(s[mid-]-s[i-])+(s[j]-s[mid])-a[mid]*(j-mid);//w数组存的是区间的误差
}
for (int i=; i<=n+; i++)
for(int j=; j<=m+; j++)
f[i][j]=;
f[][]=;
for (int i=; i<=n; i++)
for (int j=; j<=m; j++)
for (int k=; k<=i-; k++)
f[i][j]=min(f[i][j],f[k][j-]+w[k+][i]);
cout<<f[n][m]<<endl;
return ;
}