This post is written in Chinese. Please consider using Google Translate

这是一个动态规划的问题。对于题中给定的A(k)的定义，我们可以很容易发现累积误差最小的情况为取A(k)为这组数的中值（不是严格意义上的中位 数，是数列S[i]..S[j]中的S[(i+j+1)/2] /为整除）。于是我们很容易想到要从小到大排序，然后以长度为阶段动态规划。

状态设定

• F[i,j] 表示前i个地区，然成j种颜色时最小的总误差。
• P[i,j] 表示排序过后的序列中，第i位到第j位的最小误差。

状态转移方程

• F[i,j]=Min{ F[k,j-1] + P[k+1,i] | 0<=k<=i-1 }

边界条件

• F[i,j]=无穷大 (0<=i<=N , 0<=j<=M)
• F[0,0]=0

P[i,j]有定义式为

• P[i,j]=Sum{ Abs( S[k]-Mid(i,j) ) | i<=k<=j } (Mid(i,j)为S[i]..S[j]的中值)

但是如果我们直接这样求，时间复杂度高达O(N^3 + N^2*M)，关键在于求P[i,j]时浪费了太多时间。其实我们可以递推求出P[i,j]。

递推式

• P[i,j]=P[i+1,j] + Mid(i,j) - S[i]

边界

• P[i,i]=0

这样，我们就可以在O(N^2*M)内解决。

/* 
 * Problem: POI1999 map
 * Author: Guo Jiabao
 * Time: 2008.12.15 20:43:18
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN=3001;
const int MAXM=11;
const int INF=0x7FFFFFF;

int N,M,Ans;
int S[MAXN];
int P[MAXN][MAXN],F[MAXN][MAXM];

int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}

void init()
{
    int i,j;
    freopen("map.in","r",stdin);
    freopen("map.out","w",stdout);
    scanf("%d%d",&N,&M);
    for (i=1;i<=N;i++)
        scanf("%d",&S[i]);
    qsort(S+1,N,sizeof(S[0]),cmp);
    for (i=0;i<=N;i++)
        for (j=0;j<=M;j++)
            F[i][j]=INF;
    F[0][0]=0;
}

void dynamic()
{
    int i,j,k;
    for (j=1;j<=N;j++)
    {
        P[j][j]=0;
        for (i=j-1;i>=1;i--)
        {
            P[i][j]=P[i+1][j]+S[(i+j+1)/2]-S[i];
        }
    }
    for (i=1;i<=N;i++)
    {
        for (j=1;j<=M;j++)
        {
            F[i][j]=INF;
            for (k=0;k<=i-1;k++)
            {
                if (F[k][j-1] + P[k+1][i] < F[i][j])
                    F[i][j] = F[k][j-1] + P[k+1][i];
            }
        }
    }
    Ans=F[N][M];
}

int main()
{
    init();
    dynamic();
    printf("%d",Ans);
    return 0;
}

<h2><span class="mw-headline">地图着色</span></h2>

在Byteland新的行政划分以后，制图工作室需要制作国家新的统计地图。因为技术上的原因，仅有很少的颜色能够被使用。地图上有着相同或者相似的人口（居民数）的地区被着为相同的颜色。对于给定的颜色K，让A（k）为数字，意思为：
<ol>
    <li>至少有一半颜色为k的地区人口不大于A（k）。</li>
    <li>至少有一半颜色为k的地区人口不少于A（k）。</li>
</ol>
地区的着色误差是指A（k）与地区人口之间的差额的绝对值，累积误差是指所有地区的着色误差之和。我们寻找一种地图的最佳着色方案（即最小的累积误差）

任务

写一个程序：
<ol>
    <li>从输入文件读取Byteland地区的人口，</li>
    <li>计算最小的累积误差，</li>
    <li>把结果写到文件中。</li>
</ol>
输入

在输入文件的首行有一个整数n（10&lt; n &lt;3000），它是Byteland的地区数。第二行有数字m（2 &lt;= m &lt;= 10），表示用于着色的颜色数。在接下来的n行中的每一行里有一个非负的整数- Byteland一个地区的人口数。注：人口数不超过2^30。

输出

你的程序应该在输出文件单独的一行里写下一个整数—等于能够完成地图最佳着色的最小累积误差。

样例输入
<pre>11
3
21
14
6
18
10
2
15
12
3
2
2</pre>
样例输出
<pre>15</pre>