Post Office
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 15258 | Accepted: 8266 |
Description
There is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each village is identified with a single integer coordinate. There are no two villages in the same position. The distance between two positions is the absolute value of the difference of their integer coordinates.
Post offices will be built in some, but not necessarily all of the villages. A village and the post office in it have the same position. For building the post offices, their positions should be chosen so that the total sum of all distances between each village and its nearest post office is minimum.
You are to write a program which, given the positions of the villages and the number of post offices, computes the least possible sum of all distances between each village and its nearest post office.
Input
Your program is to read from standard input. The first line contains two integers: the first is the number of villages V, 1 <= V <= 300, and the second is the number of post offices P, 1 <= P <= 30, P <= V. The second line contains V integers in increasing order. These V integers are the positions of the villages. For each position X it holds that 1 <= X <= 10000. Output
The first line contains one integer S, which is the sum of all distances between each village and its nearest post office. Sample Input
10 5 1 2 3 6 7 9 11 22 44 50
Sample Output
9
【Poj-1160 Post Office(经典dp】Source
IOI 2000
题目大意：对于一条直线上的v个村子，要建造p个邮局，邮局只能建在村子里，给定了村子的位置，求所有村子到达邮局的距离之和最小是多少。
方法：
用dp[i][j]表示前i个村子建造j个邮局的最优解，那么最终答案即为dp[v][p].
用sum[i][j]来表示第i个村子到第j个村子建造1个邮局的最优解，那么sum[i][j]=sum[i][j-1]+(map[j]-map[(i+j)/2]);
因为只需建造1个邮局时一定是建在中点最优（偶数个的话则中间两个点都一样）,
若之前有偶数个村子（i->j-1），在此基础上再加一个j，变成奇数个村子，之前的中点（较靠后的那个）恰好也是现在的中点，那么只需再加上j到中点的距离即可
若之前有奇数个村子，同理~
至此，dp[i][j]=min{dp[i][j],dp[k][j-1]+sum[k+1][i]} (j-1<=k
代码：
#include
#include
#includeusing namespace std;
const int lin=305;
int map[lin],sum[lin][lin],dp[lin][35];
bool vis[lin][35];
inline int smi(int x,int y)
{
if(x>v>>p)
{
memset(map,0,sizeof(map));
for(int i=1;
i<=v;
++i)
{
scanf("%d",&map[i]);
}memset(sum,0,sizeof(sum));
for(int i=1;
i<=v;
++i)
{
for(int j=i+1;
j<=v;
++j)
{
sum[i][j]=sum[i][j-1]+map[j]-map[(i+j)/2];
}
}memset(vis,0,sizeof(vis));
for(int i=1;
i<=v;
++i)
{
dp[i][1]=sum[1][i];
vis[i][1]=true;
}cout< 推荐阅读
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- 数据结构与算法|【算法】力扣第 266场周赛
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- 动态规划|暴力递归经典问题
- 动态规划|动态规划 —— 状压DP (附一些位运算小知识)
- 区间DP —— 能量项链
- 动态规划 —— 区间DP
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element
- LeetCode-28 实现strStr() KMP算法
- leetcode|递归、动态规划--Leetcode(python)