博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU_1227_Fast Food_动态规划
阅读量:7113 次
发布时间:2019-06-28

本文共 2821 字,大约阅读时间需要 9 分钟。

链接:

Fast Food

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 2695    Accepted Submission(s): 1142

Problem Description
The fastfood chain McBurger owns several restaurants along a highway. Recently, they have decided to build several depots along the highway, each one located at a restaurant and supplying several of the restaurants with the needed ingredients. Naturally, these depots should be placed so that the average distance between a restaurant and its assigned depot is minimized. You are to write a program that computes the optimal positions and assignments of the depots. 
To make this more precise, the management of McBurger has issued the following specification: You will be given the positions of n restaurants along the highway as n integers d1 < d2 < ... < dn (these are the distances measured from the company's headquarter, which happens to be at the same highway). Furthermore, a number k (k <= n) will be given, the number of depots to be built. 
The k depots will be built at the locations of k different restaurants. Each restaurant will be assigned to the closest depot, from which it will then receive its supplies. To minimize shipping costs, the total distance sum, defined as
must be as small as possible.
Write a program that computes the positions of the k depots, such that the total distance sum is minimized. 
 

 

Input
The input file contains several descriptions of fastfood chains. Each description starts with a line containing the two integers n and k. n and k will satisfy 1 <= n <= 200, 1 <= k <= 30, k <= n. Following this will n lines containing one integer each, giving the positions di of the restaurants, ordered increasingly.
The input file will end with a case starting with n = k = 0. This case should not be processed. 
 

 

Output
For each chain, first output the number of the chain. Then output a line containing the total distance sum. 
Output a blank line after each test case.
 

 

Sample Input
6 3 5 6 12 19 20 27 0 0
 

 

Sample Output
Chain 1 Total distance sum = 8
 
一来没思路,看了题解,目前动态规划的题几乎都看了题解才有思路。。。。。。
思路:[i,j]之间加一个仓库,为了使要增加的路程最短,只能加在第(int)(i+j)/2个餐厅。
case[i][j]为在[i,j]之间加一个仓库所要增加的路程。
dp[i][j]表示在前j个餐厅之中加i个仓库所要走的路程。
状态转移方程:dp[i][j]=min(dp[i][j],dp[i-1][m]+case[m+1][j]);  (i-1<=m<=j-1)
 
#include
#include
#include
#include
using namespace std;#define LL long longint dis[205];int dist[205][205];int dp[35][205];int main(){ int n,k,cases=1; while(scanf("%d%d",&n,&k)!=EOF&&n&&k) { memset(dist,0,sizeof(dist)); for(int i=0; i<=k; i++) for(int j=0; j<=n; j++) dp[i][j]=2000000000; //cout<
View Code

 

转载于:https://www.cnblogs.com/jasonlixuetao/p/5468589.html

你可能感兴趣的文章
Python 数据结构_队列
查看>>
NAS数据迁移初探
查看>>
打破医院围墙 数字化平台之上的想象力
查看>>
Teradata首席分析官Bill Franks:数据分析变革犹如一场工业革命
查看>>
Linux下安装并使用Java开发opencv的配置
查看>>
AdTime: DMC量身定制的企业数据分析师
查看>>
《数字逻辑设计与计算机组成》一2.3 规范表达式
查看>>
借道大数据 互联网基金再探“蓝海”
查看>>
浙江医疗综合体获批 医疗资源也可共享
查看>>
3G/4G调制解调器曝漏洞:可致设备被完全控制
查看>>
你知道你的Mac摄像头正在偷窥你吗?这款工具或许能帮你
查看>>
超干货!一套完整的设计分析思路应该是怎样的?
查看>>
关于视频流的各种问题,后续整理
查看>>
从零开始,我的上云路
查看>>
【Spark Summit East 2017】R与Spark:如何使用RStudio的 Sparklyr和H2O的 Rsparkling分析数据...
查看>>
FIS源码-fis release概览
查看>>
鹰眼跟踪、EDAS燎原, 看高性能服务框架EDAS的架构实践
查看>>
使用LogHub进行日志实时采集
查看>>
使用jackson-mapper-lgpl序列化和反序列化
查看>>
Windows环境下在Oracle VM VirtualBOX下克隆虚拟机镜像(克隆和导入)
查看>>