P1220 关路灯【洛谷算法习题】

P1220 关路灯网页链接P1220 关路灯题目描述某一村庄在一条路线上安装了n nn盏路灯每盏灯的功率有大有小即同一段时间内消耗的电量有多有少。老张就住在这条路中间某一路灯旁他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。为了给村里节省电费老张记录下了每盏路灯的位置和功率他每次关灯时也都是尽快地去关但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率然后选择先关掉功率大的一边再回过头来关掉另一边的路灯而事实并非如此因为在关的过程中适当地调头有可能会更省一些。现在已知老张走的速度为1 m / s 1m/s1m/s每个路灯的位置是一个整数即距路线起点的距离单位m mm、功率W WW老张关灯所用的时间很短而可以忽略不计。请你为老张编一程序来安排关灯的顺序使从老张开始关灯时刻算起所有灯消耗电最少灯关掉后便不再消耗电了。输入格式第一行是两个数字n nn表示路灯的总数和c cc老张所处位置的路灯号接下来n nn行每行两个数据表示第1 11盏到第n nn盏路灯的位置和功率。数据保证路灯位置单调递增。输出格式一个数据即最少的功耗单位J JJ1 J 1 W × s 1J1W\times s1J1W×s。输入输出样例 #1输入 #15 3 2 10 3 20 5 20 6 30 8 10输出 #1270说明/提示样例解释此时关灯顺序为3 4 2 1 5。数据范围1 ≤ n ≤ 50 1\le n\le501≤n≤501 ≤ c ≤ n 1\le c\le n1≤c≤n1 ≤ W i ≤ 100 1\le W_i \le 1001≤Wi​≤1001 ≤ 路灯位置 ≤ 100 1 \leq \text{路灯位置} \leq 1001≤路灯位置≤100解题思路解题思路本题是区间动态规划的经典问题。老张关灯的过程可以看作是在一条直线上不断扩展已关灯的连续区间因此可以用区间 DP 来求解最小功耗。1. 问题等价转化路灯按位置升序排列老张从第c cc盏灯出发每次关掉一盏灯。由于他只会走向相邻的未关路灯因此任意时刻已经关掉的路灯必然构成一个连续的区间[ i , j ] [i, j][i,j]。老张关灯后可能停在区间的左端点i ii或右端点j jj因此需要两个状态来区分。功耗 时间 × 功率。老张行走速度为1 m/s 1\,\text{m/s}1m/s所以行走时间等于行走距离。在行走过程中所有尚未关掉的路灯仍在耗电。因此每次移动的功耗 移动距离 × 当前未关路灯的总功率。2. 动态规划设计状态定义F[i][j][0]关掉区间[ i , j ] [i, j][i,j]的所有路灯后老张停在左端点i ii时的最小总功耗。F[i][j][1]关掉区间[ i , j ] [i, j][i,j]的所有路灯后老张停在右端点j jj时的最小总功耗。前缀和S[i]表示前i ii盏灯的总功率。关掉区间[ i , j ] [i, j][i,j]后未关路灯包括[ 1 , i − 1 ] [1, i-1][1,i−1]和[ j 1 , n ] [j1, n][j1,n]其总功率为rem ( i , j ) S [ i − 1 ] S [ n ] − S [ j ] \text{rem}(i, j) S[i-1] S[n] - S[j]rem(i,j)S[i−1]S[n]−S[j]但在转移过程中需要注意移动时目标灯尚未关掉因此计算功耗时未关灯的总功率应包含目标灯。例如从i 1 i1i1走到i ii时此时i ii还未关所以未关灯总功率为S [ i ] S [ n ] − S [ j ] S[i] S[n] - S[j]S[i]S[n]−S[j]因为[ i 1 , j ] [i1, j][i1,j]已关。转移方程区间长度len从2 22到n nn对于区间[ i , j ] [i, j][i,j]j i l e n − 1 j i len - 1jilen−1考虑最后一步若最后停在i ii则上一步可能停在i 1 i1i1从i 1 i1i1向左走到i ii或停在j jj从j jj一路向左走到i iiF [ i ] [ j ] [ 0 ] min ⁡ { F [ i 1 ] [ j ] [ 0 ] ( X [ i 1 ] − X [ i ] ) × ( S [ i ] S [ n ] − S [ j ] ) F [ i 1 ] [ j ] [ 1 ] ( X [ j ] − X [ i ] ) × ( S [ i ] S [ n ] − S [ j ] ) F[i][j][0] \min \begin{cases} F[i1][j][0] (X[i1] - X[i]) \times (S[i] S[n] - S[j]) \\ F[i1][j][1] (X[j] - X[i]) \times (S[i] S[n] - S[j]) \end{cases}F[i][j][0]min{F[i1][j][0](X[i1]−X[i])×(S[i]S[n]−S[j])F[i1][j][1](X[j]−X[i])×(S[i]S[n]−S[j])​若最后停在j jj则上一步可能停在j − 1 j-1j−1从j − 1 j-1j−1向右走到j jj或停在i ii从i ii一路向右走到j jjF [ i ] [ j ] [ 1 ] min ⁡ { F [ i ] [ j − 1 ] [ 0 ] ( X [ j ] − X [ i ] ) × ( S [ i − 1 ] S [ n ] − S [ j − 1 ] ) F [ i ] [ j − 1 ] [ 1 ] ( X [ j ] − X [ j − 1 ] ) × ( S [ i − 1 ] S [ n ] − S [ j − 1 ] ) F[i][j][1] \min \begin{cases} F[i][j-1][0] (X[j] - X[i]) \times (S[i-1] S[n] - S[j-1]) \\ F[i][j-1][1] (X[j] - X[j-1]) \times (S[i-1] S[n] - S[j-1]) \end{cases}F[i][j][1]min{F[i][j−1][0](X[j]−X[i])×(S[i−1]S[n]−S[j−1])F[i][j−1][1](X[j]−X[j−1])×(S[i−1]S[n]−S[j−1])​注意在计算F[i][j][0]时未关灯总功率为S [ i ] S [ n ] − S [ j ] S[i] S[n] - S[j]S[i]S[n]−S[j]在计算F[i][j][1]时未关灯总功率为S [ i − 1 ] S [ n ] − S [ j − 1 ] S[i-1] S[n] - S[j-1]S[i−1]S[n]−S[j−1]。这是因为移动的目标灯不同目标灯在到达前尚未关掉。边界条件初始状态F[c][c][0] F[c][c][1] 0只有第c cc盏灯被关老张就在该位置。其他所有F初始化为一个极大值代码中用memset(F, 127, sizeof(F))实现即将每个字节设为0x7f对long long而言是一个很大的数。最终答案min(F[1][n][0], F[1][n][1])即关掉所有灯后无论老张停在左端还是右端的最小功耗。3. 复杂度分析时间复杂度状态数为O ( n 2 ) O(n^2)O(n2)每个状态转移O ( 1 ) O(1)O(1)总时间复杂度O ( n 2 ) O(n^2)O(n2)。n ≤ 50 n \le 50n≤50运算量极小。空间复杂度需要存储三维 DP 数组F[60][60][2]以及位置、功率、前缀和数组空间复杂度O ( n 2 ) O(n^2)O(n2)完全可接受。总结将关灯过程建模为区间扩展用两个状态分别表示老张停在区间左端或右端。转移时考虑从相邻区间扩展而来并乘以当前未关路灯的总功率即剩余灯仍在耗电。通过前缀和快速计算未关灯总功率实现O ( 1 ) O(1)O(1)转移。该方法思路清晰是区间 DP 在资源调度类问题中的典型应用。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll MAXM60;ll X[MAXM],Y[MAXM],S[MAXM],n,c;ll F[MAXM][MAXM][2];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld%lld,n,c);memset(F,127,sizeof(F));for(ll i1;in;i){scanf(%lld%lld,X[i],Y[i]);S[i]S[i-1]Y[i];}F[c][c][0]F[c][c][1]0;for(ll len2;lenn;len){for(ll i1;ilen-1n;i){ll jilen-1;F[i][j][0]min(F[i1][j][0](X[i1]-X[i])*(S[i]S[n]-S[j]),F[i1][j][1](X[j]-X[i])*(S[i]S[n]-S[j]));F[i][j][1]min(F[i][j-1][0](X[j]-X[i])*(S[i-1]S[n]-S[j-1]),F[i][j-1][1](X[j]-X[j-1])*(S[i-1]S[n]-S[j-1]));}}ll ansmin(F[1][n][0],F[1][n][1]);printf(%lld,ans);return0;}