POI 1999 地圖着色 Map
本文正體字版由OpenCC轉換
這是一個動態規劃的問題。對於題中給定的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< n <3000），它是Byteland的地區數。第二行有數字m（2 <= m <= 10），表示用於着色的顏色數。在接下來的n行中的每一行裏有一個非負的整數- Byteland一個地區的人口數。注：人口數不超過2^30。
輸出
你的程序應該在輸出文件單獨的一行裏寫下一個整數—等於能夠完成地圖最佳着色的最小累積誤差。
樣例輸入
<pre>11
3
21
14
6
18
10
2
15
12
3
2
2</pre>
樣例輸出
<pre>15</pre>
上次修改時間 2017-02-03