Beyond the Void
BYVoid
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&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>

上次修改時間 2017-02-03

相關日誌