关路灯

测试数据来自 system/1182

作业已超过截止时间,您无法递交本题目。

时间限制:1秒  内存限制:256M


【问题描述】

  某一村庄在一条路线上安装了 \(N\) 盏灯(依次标号 \(1..N\)),每盏灯都有各自的位置和功率(即每秒消耗的电量)。

  老张就住在路灯 \(P\) 旁,他每天早上的第一件事就关掉这些路灯:首先会关掉路灯 \(P\),然后可以向左也可以向右去关其他灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率,然后选择先关掉功率大的一边,再回过头来关掉另一边的路灯,而事实并非如此,因为在关的过程中适当地调头有可能会更省一些。

  已知老张走的速度为 \(1m/s\),老张关灯所用的时间可以忽略不计。请你编一程序来安排老张的关灯顺序,使从老张开始关灯时刻算起所有灯的耗电量之和最少。

【输入格式】

  第一行包含一个整数 \(N\) 表示该村庄路灯的数量。
  第二行包含一个整数 \(P(1≤P≤N)\),表示老张开始在路灯 \(P\) 旁。
  接下来有 \(N\) 行,每行包含两个整数:\(X\) 和 \(W\)。表示路灯路线开始处的距离为 \(X\) 米,功率为 \(W\) 瓦。路灯是按顺序给定的。

【输出格式】

  输出一个整数,即耗电量的最小值。

【输入输出样例】

 Input

5
3
2 10
3 20
5 20
6 30
8 10

 Output

270

【数据限制】

  对于 \(20\%\) 数据有:\(N≤25\);
  对于 \(50\%\) 数据有:\(N≤50\);
  对于 \(100\%\) 数据有:\(N≤1000,0≤X≤10000,0≤W≤1,000,000,000\)。

【来源】

  Mr.he

区间动态规划练习题

未认领
状态
已结束
题目
10
开始时间
2025-03-21 00:00
截止时间
2025-04-30 23:59
可延期
24.0 小时