若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1718: 有向直线2中值问题

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,492

题目描述

给定一条有向直线L以及L上的n+1个点x0 < x1 < …… < xn。有向直线L上的每个点xi都有一个权w(xi);每条有向边(xi,xi-1)也都有一个非负边长d(xi,xi-1)。有向直线L上的每个点xi可以看作客户,其服务需求量为w(xi)。每条边(xi,xi-1)的边长d(xi,xi-1)可以看作运输费用。如果在点xi处未设置服务机构,则将点xi处的服务需求沿有向边转移到点xj处服务机构需付出的服务转移费用为w(xi)*d(xi,xj)。在点x0处已设置了服务机构,现在要在直线L上增设2处服务机构,使得整体服务转移费用最小。对于给定的有向直线L,计算在直线L上增设2处服务机构的最小服务转移费用。

输入

输入数据的第1行有1个正整数n(n≤20000),表示有向直线L上除了点x0外还有n个点x0 < x1 < ……< xn。接下来的n行中,每行有2个整数。第i+1行的2个整数分别表示w(xn-i-1)和d(xn-i-1,xn-i-2)。

输出

输出只有一个整数,表示最小服务转移费用。

样例输入

9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1

样例输出

26

参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Skip 原站点 Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist