POI 1999 地图着色 Map
这是一个动态规划的问题。对于题中给定的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