DP .首先求出任意两个村庄间(包括端点)建一个邮局后,到邮局的最短距离和,记为min_dis[i][j],当邮局建到中点时min_dis[i][j]最小. 用f[i][j]表示前i个邮局建在前j个村庄.则f[i][j]=min{f[i-1][k]+min_dis[k+1][j]，i-1<=k<j}.见代码：
#include<iostream>
using namespace std;
int v,p;
int vill[305];
int f[35][305];
int min_dis[305][305];
int main()
{
int i,j,k;
scanf("%d%d",&v,&p);
for(i=1;i<=v;i++)
scanf("%d",&vill[i]);
memset(min_dis,0,sizeof(min_dis));
for(i=1;i<=v;i++)
for(j=i+1;j<=v;j++)
{
int mid=(i+j)/2;
for(k=i;k<mid;k++)
{
min_dis[i][j]+=vill[mid]-vill[k];
}
for(k=mid+1;k<=j;k++)
{
min_dis[i][j]+=vill[k]-vill[mid];
}
}
for(i=1;i<=v;i++) f[1][i]=min_dis[1][i];
for(i=2;i<=p;i++)
for(j=i;j<=v;j++)
{
int minn=100000000;
for(k=i-1;k<=j-1;k++)
{
if(f[i-1][k]+min_dis[k+1][j]<minn)
minn=f[i-1][k]+min_dis[k+1][j];
}
f[i][j]=minn;
}
printf("%d\n",f[p][v]);
//system("pause");
return 0;
}
posted on 2010-08-19 12:45
wuxu 阅读(151)
评论(0) 编辑 收藏 引用 所属分类:
动态规划