poj-1160 post office (dp)

題意：

 根據每個村莊的距離，在這些村莊裡建一些office使得每個村莊到最近的office距離和最短。

分析：

 如果此題建一個office，那麼很容易得到，隻要建在中間，就一定是最小的。這就是中值最小法，而這題是建立多個office，那麼應該區間dp。

設dp[i][j]在前j個村莊也建立了i個office。對于每個區間i到j，取中間的作為建立點。用dis記錄每個區間最短距離。

那麼轉移狀态方程： dp[i][j]=min(dp[i][j],dp[i-1][j]+dis[j+1][j])

參考代碼：

#include<cstdio>
#include<algorithm>
using namespace std;
#define INF 1<<29
const int N=305;
int dp[35][N];
int dis[N][N];
int n,m;
void solve()
{
	int i,j,k;
	for(i=1;i<=n;i++){
		dp[1][i]=dis[1][i];
	}
	for(i=2;i<=m;i++){
		for(j=i+1;j<=n;j++){
			dp[i][j]=INF;
			for(k=j-1;k>=i-1;k--)
			dp[i][j]=min(dp[i][j],dp[i-1][k]+dis[k+1][j]);
		}
	}
	printf("%d\n",dp[m][n]);
}
int main()
{
	int i,j;
	int vil[N];
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%d",&vil[i]);
	}
	for(i=1;i<n;++i){
		for(j=i+1;j<=n;j++){
			dis[i][j]=dis[i][j-1]+vil[j]-vil[(i+j)>>1];
		}
	}
	solve();
}