给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;
}
分享到:
相关推荐
本题是一道很好的树状 DP 的练习题,它不仅考验了对动态规划的理解,还涉及到了图论中的树结构。通过解决这类问题,可以加深对动态规划思想的认识,掌握如何在树结构上应用动态规划技术解决实际问题。
### poj dp总结:动态规划分类 #### 概述 动态规划(Dynamic Programming,简称DP)是一种在计算机科学和数学中广泛使用的算法策略,用于解决最优化问题。它通过将复杂问题分解为较简单的子问题来求解,并利用这些...
【强大的POJ分类——各类编程简单题及其算法分类】 POJ,全称为Peking University Online Judge,是北京大学提供的一个在线编程题目平台,支持多种编程语言,包括Pascal、C、C++、Java、Fortran、Python等。这个...
根据标题“poj 1191 经典dp 源代码”和描述中的信息,可以推测此题目是一个经典的动态规划问题。题目要求通过划分一个二维矩阵为多个不重叠的矩形区域,使得每个矩形区域的平均值与整体平均值之差的平方和最小。这个...
poj训练 c语言poj训练 西工大 poj 100题。
【标题】:“西工大poj习题” 这个标题指的是来自西安工业大学(Xi'an Jiaotong University,简称“西工大”)的POJ(Problem Oriented Judgment)在线编程练习平台上的习题集合。POJ是一个面向大学生的在线编程...
标题中的"POJ第1861题源码"指的是编程竞赛网站POJ(Programming Online Judge)上的第1861道题目,该题目通常会涉及到一个特定的算法或编程问题,而源码则指的是参赛者提交的解决该问题的程序代码。在描述和标签中...
根据题目要求,以下是从“poj推荐50题”中提炼出的相关知识点: ### 第一类:动态规划 #### 重要性: 动态规划是算法学习中的重要组成部分,它可以帮助解决许多复杂的问题,通过将问题分解为更小的子问题来求解。 ...
poj2009离线题库 poj2009离线题库
* 型如下表的简单 DP:型如下表的简单 DP 是指解决问题的简单 DP 算法,如 poj3267、poj1836、poj1260、poj2533。 * 计算几何学:计算几何学是指解决问题的计算几何学算法,如 poj2031、poj1039。 六、数学 数学...
在编程竞赛领域,POJ(Programming Online Judge)是一个知名的在线评测系统,主要针对ACM(国际大学生程序设计竞赛)的训练。ACM竞赛是全球范围内的一个编程比赛,旨在提升大学生的算法设计、编程和问题解决能力。...
标题“PKU 、POJ ACM/ICPC300多题的代码”指的是北京大学(PKU)和编程在线评测平台POJ上收集的300多道ACM/ICPC(国际大学生程序设计竞赛)比赛题目解题代码。这个压缩包包含了解决这些竞赛问题的算法和程序实现,是...
标题中的“poj acm300题 c++源码打包”表明这是一份包含300个在POJ(编程在线判题系统)上已通过的ACM竞赛题目解决方案的压缩文件,语言为C++。ACM,即国际大学生程序设计竞赛(International Collegiate ...
【北大POJ水题-整合包】是一个针对北京大学(Peking University)在线判题系统POJ(Peking University Online Judge)中的基础题目所整理的资源集合。这个整合包包含了对这些"水题"的解题报告和已经通过验证...
* 1160 Post Office:本题目使用动态规划来计算邮局的最短距离。 * 1458 Common Subsequence:本题目使用动态规划来计算两个序列的最长公共子序列。 * 1579 Function Run Fun:本题目使用动态规划来计算函数的执行...
【标题】"POJ题目简单分类(ACM)" 涉及的知识点: 【描述】中的"学习起来更系统,更清爽"暗示了本话题旨在为ACM竞赛初学者提供一个有条理的学习路径。 【标签】"POJ 分类"表明我们将探讨的是基于POJ(Problemset On...
3. "POJ3411-Paid Roads.doc":这很可能是解题报告,详细记录了解题思路、算法设计过程、代码解释等,帮助读者理解如何解决这个问题。 从编程竞赛的角度来看,"Paid Roads"可能是一个涉及图论的问题,可能需要处理...
poj题目,需要可以下载,虽然没有包含所有的题目,但是对初级入门有帮助
【标题】"POJ3717题的代码"涉及的是一个编程竞赛中的问题,POJ(Problem Set of Peking University)是北京大学主办的一个在线编程练习平台,它提供了许多算法题目供参赛者解决。这个标题表明我们要讨论的是针对POJ...