给n个村子建p个邮局,求最佳的建设方案使得每个村子到最近的邮局的距离和最短,输出最短距离。
首先递推求出n个村子建1个邮局的最佳方案,画下图很容易理解。
再递推求解多个邮局的最佳方案,具体的看注释吧。
/*
//k从1枚举到i-1就够了
dp[i][j]=min(dp[i][j],dp[k][j-1]+sum[k+1][i]);
这个画下图很好推出来的。
sum[i][j]=sum[i][j-1]+p[j]-p[(i+j)/2];
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int sum[305][305]; //在i到j之间建一个邮局的最小消耗
int p[305];
int dp[305][305]; //前i个村子建j个邮局的最小消耗
int main()
{
int n,k;
while(~scanf("%d%d",&n,&k))
{
memset(dp,0x3f,sizeof(dp));
memset(sum,0,sizeof(sum));
p[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
sum[i][j]=sum[i][j-1]+p[j]-p[(i+j)/2];
}
dp[i][1]=sum[1][i];
dp[i][i]=0;
}
for(int j=2;j<=k;j++)
{
for(int i=j+1;i<=n;i++)
{
for(int k=1;k<i;k++)
{
dp[i][j]=min(dp[i][j],dp[k][j-1]+sum[k+1][i]);
}
}
}
printf("%d\n",dp[n][k]);
}
return 0;
}
分享到:
相关推荐
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
PKU 、POJ ACM/ICPC300多题的代码,还有各种典型问题的分类代码
poj训练 c语言poj训练 西工大 poj 100题。
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
poj2009离线题库 poj2009离线题库
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
poj上面的300道AC题,c++源码,自己写的不会有任何问题。
POJ题目源码 共221题 含源码,题目和简单的分类
初学acmer必练题,包括图论,动态规划,和数论的基础题
西工大poj里基本所有的习题了,应该是比较新的习题总集了,1-100.
POJ 是“北京大学程序在线评测系统”(Peking University Online Judge)的缩写,是个提供编程题目的网站,兼容Pascal、C、C++、Java、Fortran、Python等多种语言。可以按照分类,在POJ上做题。
北大 POJ的水题解答C++版,请合理使用
poj题目,需要可以下载,虽然没有包含所有的题目,但是对初级入门有帮助
北大POJ水题整合包 解题报告+AC代码
西工大poj习题1-7季 快来下载吧 很有帮助的哦
用了半年的时间才做了一百多道题,没特别难的,都比较基础,大牛们远观就可以了,共151道,代码虽谈不上有多高,但也绝非垃圾。 仅供参考
POJ100题详细解题报告
北京大学在线测评网站POJ第1200题的解答,已经AC通过