P1220 关路灯题解

zengyukai2012 · 2025-10-19 09:27:04 · 题解

题目大意

一条直线上有 n 盏路灯，第 i 盏灯的位置为 wz_i（单位：米），功率为 gl_i（单位：瓦）。老张初始位于第 c 盏灯处，他需要关闭所有灯。他的行走速度为 1\,\text{m/s}，关灯时间忽略不计。

每盏灯在被关闭前持续耗电，目标是安排关灯顺序，使得从开始关灯时刻起，所有灯消耗的总电能（单位：焦耳）最小。

解题思路

1. 问题转化

总耗电量 = 每盏灯的功率 \times 它被关闭前所经过的时间。
时间 = 老张走过的路径长度（速度为 1）。

2. 区间 DP 的适用性

观察发现：

老张关灯的过程一定是从初始位置 c 开始，逐步向左或向右扩展已关灯的连续区间。
一旦区间 [i, j] 内的灯全部关闭，老张必定位于 i 或 j。
后续只能关 i-1 或 j+1。

这符合区间动态规划的典型特征。

3. 状态定义

定义：

4. 前缀和优化

设 gl\_qzh_k = \sum_{t=1}^{k} gl_t，即功率前缀和。

则任意区间外的总功率可快速计算：

区间 [i, j] 之外的灯总功率为： \text{outside}(i, j) = gl\_qzh_{i-1} + (gl\_qzh_n - gl\_qzh_j)

5. 状态转移

转移到左端点 i

从 [i+1, j] 扩展而来：

若原在 i+1：走 wz_{i+1} - wz_i；
若原在 j：走 wz_j - wz_i。

未关灯为 [1, i] \cup (j, n]，总功率为 gl\_qzh_{i} + (gl\_qzh_n - gl\_qzh_j)。

故：

f_{i,j,0} = \min\left\{ \begin{aligned} &f_{i+1,j,0} + \bigl(gl\_qzh_{i} + gl\_qzh_n - gl\_qzh_j\bigr) \cdot (wz_{i+1} - wz_i), \\ &f_{i+1,j,1} + \bigl(gl\_qzh_{i} + gl\_qzh_n - gl\_qzh_j\bigr) \cdot (wz_j - wz_i) \end{aligned} \right.

转移到右端点 j

从 [i, j-1] 扩展而来：

若原在 i：走 wz_j - wz_i；
若原在 j-1：走 wz_j - wz_{j-1}。

未关灯为 [1, i) \cup [j, n]，总功率为 gl\_qzh_{i-1} + (gl\_qzh_n - gl\_qzh_{j-1})。

故：

f_{i,j,1} = \min\left\{ \begin{aligned} &f_{i,j-1,0} + \bigl(gl\_qzh_{i-1} + gl\_qzh_n - gl\_qzh_{j-1}\bigr) \cdot (wz_j - wz_i), \\ &f_{i,j-1,1} + \bigl(gl\_qzh_{i-1} + gl\_qzh_n - gl\_qzh_{j-1}\bigr) \cdot (wz_j - wz_{j-1}) \end{aligned} \right.

6. 初始状态与答案

初始：f_{c,c,0} = f_{c,c,1} = 0；
其余状态初始化为 +\infty；
最终答案：\min(f_{1,n,0}, f_{1,n,1})。

代码实现

#include <bits/stdc++.h>
using namespace std;
int n /*路灯总数*/, c /*初始位置*/;
int wz[51] /*路灯位置*/, gl[51] /*功率*/;
int gl_qzh[51] /*功率的前缀和*/;
int f[51][51][2];
// f[i][j][0] 表示关闭从 i 到 j 的灯，现在在 i 处的总功率
// f[i][j][1] 表示关闭从 i 到 j 的灯，现在在 j 处的总功率
int main()
{
    cin >> n >> c;
    for (int i = 1; i <= n; ++i)
        cin >> wz[i] >> gl[i];
    for (int i = 1; i <= n; ++i)
        gl_qzh[i] = gl_qzh[i - 1] + gl[i];
    memset(f, 0x3f, sizeof(f)); // 初始为最大值 
    f[c][c][0] = f[c][c][1] = 0; // 初始位置
    for (int l = 1; l <= n; ++l) // 枚举区间长度 
        for (int i = 1; i <= n - l; ++i) // 枚举起点 
        {
            int j = i + l; // 终点 
            f[i][j][0] = min // 去 i 处 
            (
                f[i + 1][j][0] + // 从 i + 1 处出发 
                (gl_qzh[i] + (gl_qzh[n] - gl_qzh[j])) /*[1, i] ∪ (j, n]*/ * (wz[i + 1] - wz[i]) /*距离*/,
                f[i + 1][j][1] + // 从 j 处出发 
                (gl_qzh[i] + (gl_qzh[n] - gl_qzh[j])) /*[1, i] ∪ (j, n]*/ * (wz[j] - wz[i]) /*距离*/
            ); 
            f[i][j][1] = min // 在 j 处 
            (
                f[i][j - 1][0] + // 从 i 处出发 
                (gl_qzh[i - 1] + (gl_qzh[n] - gl_qzh[j - 1])) /*[1, i) ∪ [j, n]*/ * (wz[j] - wz[i]) /*距离*/,
                f[i][j - 1][1] + // 从 j - 1 处出发 
                (gl_qzh[i - 1] + (gl_qzh[n] - gl_qzh[j - 1])) /*[1, i) ∪ [j, n]*/ * (wz[j] - wz[j - 1]) /*距离*/
            );
        }
    cout << min(f[1][n][0], f[1][n][1]) << '\n';
}

P1220 关路灯 题解