首页 > 试题广场 >

wyh的问题

[编程题]wyh的问题
  • 热度指数:14 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

我国现在能源消耗非常严重,现在政府有这样一个工作,每天早上都需要把一些路灯关掉,但是他们想让在关闭的过程中所消耗的能源是最少的,负责路灯关闭的工作人员以1m/s的速度进行行走,假设关闭路灯的时候不需要花费任何的时间,请你编写一个程序,计算在给定路灯位置和每个路灯的消耗能源的多少,求出当所有路灯关闭的时候所需要的最少能量


输入描述:
多组测试数据循环输入
每组测试数据第一行:N表示路灯的数量 (2<=N <=1000)
第二行:V表示开始关灯的路灯号码。 (1<=V<=N)
接下来的N行中,每行包含两个用空格隔开的整数D和W,用来描述每盏灯的参数
D表示该路灯到原点的距离 (用米为单位来表示),
W表示灯泡的功率,即每秒该灯泡所消耗的能量数。(0<=D<=1000,0<=W<=1000)
路灯按照顺序给出,起始位置的那盏灯不算消耗的电能里面


输出描述:
输出一个整数,即消耗能量之和的最小值。
示例1

输入

4
3
2 2
5 8
6 1
8 7

输出

56

说明

对于样例,我一开始在第三个路灯的位置,即在6位置
第1s的时候去5把第二盏灯关闭,消耗电能8
然后去第四盏灯,第四盏灯亮的时间是4s 所以消耗电能28
最后去关第一盏灯第一盏灯亮的时间是10s 所以消耗电能20
最后总和为8+28+20=56
头像 cheese_case
发表于 2022-01-10 17:26:46
本题与普通区间dp有一些区别,下面我悉数道来 首先决策:每次一次的决策(往左或者往右走),发现其一定是一个连续区间关闭; 关于本题与常规区间dp的区别:完成一个区间时最优解一定停在区间两端,而从小区间推至大区间的过程,要考虑距离成本 故小区间所停在的左右端点不同对后续造成影响,故要将其纳入状态; 展开全文
头像 流锡
发表于 2021-10-14 20:14:27
思路: 区间dp 设dp[l][r]表示[l,r]区间人在左端点里最小的耗电值 dp[r][l]表示[l,r]区间人在右端点的最小值 设起点为st 因为l<=st,r>=st所以这样设置dp不会有重叠的情况 然后就推方程啦 先用前缀和记录前i个电灯的每秒耗电量 同时可以注意到人在左端点的 展开全文