這是一個動態規劃的問題。對於題中給定的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>