首页 > 代码库 > DSY2933*地图

DSY2933*地图

2024-08-29 12:54:38   218人阅读

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
 
首先将各个区域按人口大小排序，这样就可以一段一段取，那么问题就变成了将n个区域分成m段，使各段区域颜色误差之和最小，可以用动归来实现：
     i表示当前j这一段的结尾，k表示上一段j-1段的结尾，f[i][j]前i个数分为j段的最小值
     f[i][j]=min(f[i][j],f[k][j-1]+   k+1到i的区域区域颜色误差);
至于区域颜色误差，这里用前缀和来实现，s[i]表示到i为止的人数总和
    k+1到i的误差=a[(i+k+1)/2]*((i+k+1)/2-k)-s[(i+k+1)/2]+s[k]    +   s[i]-s[(i+k+1)/2]-a[(i+k+1)/2]*(i-(k+i+1)/2)
                                       A[k]左半边的误差                                                      A[k]右半边的误差
  
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[3333]={0},f[3333][11]={0},s[3333]={0};

int main()
{
        int n=0,m=0;
    cin>>n>>m;
    for (int i=1;i<=n;i++)
      cin>>a[i];
    sort(a+1,a+1+n);
    for (int i=1;i<=n;i++)
      s[i]=s[i-1]+a[i];
    memset(f,2^30+1,sizeof(f));
    f[0][0]=0;
    for (int i=1;i<=n;++i)
      for (int j=1;j<=m;++j)
        for (int k=0;k<i;++k)
          f[i][j]=min(f[i][j],f[k][j-1]+a[(i+k+1)/2]*((i+k+1)/2-k)-s[(i+k+1)/2]+s[k]+s[i]-s[(i+k+1)/2]-a[(i+k+1)/2]*(i-(k+i+1)/2));
    cout<<f[n][m]<<endl;
    return 0;      
}

 

　　

DSY2933*地图


联系
我们