学步园

经典动态规划题目，俺真的是太菜 了，推了好久都没推出来，最后只好学习网上大神们的报告才过的。。

dp[i][j]表示前 j 个村庄 建了i 个 邮局的最优解，cost[i][j]表示在i 和 j 之间 建立一个邮局 的最小代价，很明显，肯定是建在最中间的

那个村庄的位置上。。

那么我们可以得到 dp[i+1][j+k]=min{dp[i][j]+cost[j+1][j+k]} k+j<=V村庄数

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxV=302;
const int inf=0x3f3f3f3f;
int vpos[maxV];
int dp[maxV][maxV],cost[maxV][maxV];
int V,P;

void getcost(){
	for(int i=1;i<=V;i++){
		for(int j=i;j<=V;j++){
			int m=(i+j)>>1;
			for(int k=i;k<=j;k++)cost[i][j]+=abs(vpos[k]-vpos[m]);
		}
	}
}

void getans(){
	memset(dp,inf,sizeof(dp));
	dp[0][0]=0;
	for(int i=0;i<=P;i++){
		for(int j=0;j<=V;j++){
			if(dp[i][j]>=inf)continue;
			for(int k=1;k+j<=V;k++){
				dp[i+1][j+k]=min(dp[i+1][j+k],dp[i][j]+cost[j+1][j+k]);
				//printf("%d\n",dp[i+1][j+k]);
			}
		}
	}
}

int main(){
	scanf("%d%d",&V,&P);
	for(int i=1;i<=V;i++)scanf("%d",vpos+i);
	getcost();
	getans();
	printf("%d\n",dp[P][V]);

}