| 题目名称 | 2240. [HZOI 2016]架设电话线路 |
|---|---|
| 输入输出 | phonewire.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 gls1196
于2016-04-17加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：47， 提交：105， 通过率：44.76% | ||||
 gls1196 |
100 | 0.073 s | 0.31 MiB | C++ |
 MistyEye |
100 | 0.093 s | 0.61 MiB | C++ |
 泪寒之雪 |
100 | 0.093 s | 12.22 MiB | C++ |
 _Itachi |
100 | 0.106 s | 0.67 MiB | C++ |
|
gls1196 |
100 | 0.118 s | 0.31 MiB | C++ |
|
gls1196 |
100 | 0.157 s | 0.28 MiB | C++ |
 angel |
100 | 0.211 s | 0.55 MiB | C++ |
 FoolMike |
100 | 0.230 s | 42.64 MiB | C++ |
|
angel |
100 | 0.262 s | 0.49 MiB | C++ |
 叶寒孤舟 |
100 | 0.266 s | 0.44 MiB | C++ |
| 本题关联比赛 | |||
| test2 | |||
| 关于 架设电话线路 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @Regnig Etalsnart :
可能是氦气。  sue
2018-09-04 10:28
5楼
| ||||
|
模拟赛评测结果70分，COGS上直接AC，果然还是氧气的作用吗？
| ||||
|
动态规划一生之敌...
| ||||
|
| ||||
|
| ||||
Regnig Etalsnart
sxysxy
ONCE AGAIN【题目描述】
最近，约翰的奶牛们越来越不满足于牛棚里一塌糊涂的电话服务，于是，她们要求约翰把那些老旧的电话线换成性能更好的新电话线。新的电话线架设在已有的n根电话线杆上，第i根电话线的高度为hi，（1=<hi<=100）。电话线总是从一根电话线杆的顶端被引到相邻的那根的顶端，如果这两根电话线杆的高度hi和hj不同，那么约翰就必须支付c*abs（hi-hj）的费用，当然，你不能移动电话线杆，只能按照原有的顺序在相邻杆间架设电话线。
加高某些电话线杆能减少架设电话线的总费用，尽管这项工作也需要支付一定的费用。更准确的说，如果他把一根电话线杆加高x米的话，他需要付出x^2费用。
请你帮约翰计算一下，如果合理的进行这两项工作，他最少要在这个电话线改造工程中花多少钱。
【输入格式】
第一行输入两个数n和c，含义如上
接下来n个整数hi
【输出格式】
输出约翰完成电话线改造工程需要花费的最小费用
【样例输入】
5 2
2 3 5 1 4
【样例输出】
15
【提示】
50%数据n<=1000，70%数据n<=10000,100%数据n<=100000;
C<=100;
Hi<=100;