原题:POJ 1160
题意:
一些村庄被建立在一条笔直的高速公路边上,我们用一条坐标轴来描述这条高速公路,每一个村庄的坐标都是整数,没有两个村庄坐标相同。两个村庄间的距离,定义为它们的坐标值差的绝对值。我们需要在一些村庄建立邮局——当然,并不是每一个村庄都必须建立邮局,邮局必须被建立在村庄里,因此它的坐标和它所在的村庄坐标相同。每个村庄使用离它最近的那个
邮局,建立这些邮局的原则是:所有村庄到各自所使用的邮局的距离总和最小。
你的任务是编写一个程序,在给定了每个村庄坐标和将要建立的邮局数之后,按照上述原则,合理地选择这些邮局的位置。
求出的所有村庄到距离它最近的邮局的距离总和.
解析:
首先要知道点L到点R间放一个邮局的最短距离:
很明显奇数个时当取最中间的那个点的时候最短(不是坐标的中间,而是下标的中间),同理,偶数个时取中间两个点之间的任何位置都可以。
对于这题我们需要预处理点L和点R之间建立一个邮局的最短距离和w[l][r],状态转移方程为w[l][r] = w[l][r-1]+a[r]-a[(r+l)>>1]
上图解释:
由前面讲的知识可以得到1~5的距离和==1~4的距离和+a[5]-a[3],再画一下1~6的==1~5的+a[6]-a[3],总结为w[l][r] = w[l][r-1]+a[r]-a[(r+l)>>1]
最后是dp数组dp[i][j]代表从起点到i点间建立j个邮局的情况
是不是就有dp[i][j]=min(dp[i][j],dp[k][j-1]+w[k+1][i])
?
eg: dp[10][3]=dp[6][2]+w[7][10],1~10建3个邮局可以由1~6建2个邮局加上7~10建一个邮局转化而来
代码:
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int INF = ~0U>>1;int a[309];
int dp[309][39];
int w[309][309];
int n,m;
int main(){while(cin>>n>>m){for(int i=1;i<=n;i++)scanf("%d",&a[i]);memset(w,0,sizeof(w));for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){w[i][j]=w[i][j-1]+a[j]-a[(i+j)>>1]; }}for(int i=1;i<=n;i++){dp[i][1]=w[1][i];dp[i][i]=0;//一个邮局就是w[1][i] }for(int i=1;i<=n;i++){//末邮局位置 for(int j=2;j<=min(m,i);j++){//邮局个数,当然比点的数量少 dp[i][j] = INF; for(int k=j;k<=i-1;k++){//枚举可转移的位置,当然比邮局个数大 dp[i][j]=min(dp[i][j],dp[k][j-1]+w[k+1][i]);}}}printf("%d\n",dp[n][m]);}
}