关路灯

形式化题目

数轴上有 $n$ 盏灯，第 $i$ 盏位于整数坐标 $pos_i$ （严格递增），功率 $w_i$ 。人初始站在第 $c$ 盏灯旁并立刻关掉它，此后每秒沿数轴移动 $1$ 单位，走到某盏亮灯处即瞬间关掉。任意时刻，所有仍亮着的灯每秒各消耗 $w_i$ 的电量。求把所有灯关完的最小总耗电量。

解法路线

本题从朴素枚举到正解的推进关系如下。对比的目的是看清：暴力把「已关灯集合」当成任意子集来记，而正解利用一条结构性观察把它压成连续区间，状态数因此从 $2^n$ 降到 $n^2$ 。

层次	适用约束	做法	复杂度	相对前层的推进
暴力	$n \le 8$	枚举关灯顺序（当前所在灯 + 已关集合）	$O(2^n \cdot n^2)$	直接模拟，暴露「位置 + 集合」两个状态维度
正解	$n \le 50$	区间 DP：区间 $[l,r]$ + 停在左/右端	$O(n^2)$	用「路过即关」把集合压成连续区间，再消掉枚举顺序

关键关系：暴力的状态是「当前在哪盏灯 + 哪些灯已关」，这正是正解状态的雏形；正解证明已关集合永远是从 $c$ 向两侧连续扩张的区间，于是集合维度坍缩成两个区间端点，而「停在哪」只需区分左端或右端——因为区间外的灯不影响后续决策的最优性，只有停的位置决定下一步走多远、烧多少电。

暴力解法

适用范围

$n \le 8$ ，对拍验证用。

思路

把整个决策过程当成一个最短路/DFS 问题：

状态： $(p, mask)$ ， $p$ 为当前所站灯的编号， $mask$ 为已关灯集合（含 $c$ ）。
转移：任选一盏未关的灯 $i$ ，走过距离 $|pos_i - pos_p|$ 。这段时间里所有仍亮着的灯（包括目标灯 $i$ 自己）都在烧电，故新增耗电为 $dist \times \sum_{j \notin mask} w_j$ ；到达后关掉 $i$ 。

注意这里没有用任何「区间」假设——已关集合允许是任意子集，完全靠搜索找最优顺序。这就是它和正解的本质区别，也是它只能处理 $n\le 8$ 的原因。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * brute.cpp：P1220 小数据暴力（n<=8）。
 * 不用区间假设，直接枚举关灯顺序：状态 = (当前位置, 已关灯集合)，
 * 每步精确模拟：走向下一盏未关的灯，路上所有亮灯燃烧 (距离) 秒，到达后关掉它。
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, c;
ll pos_[10], w[10];
ll ans;

// 已关集合 mask，站在 p，当前已烧电量 cur
void dfs(int p, int mask, ll cur) {
    if (mask == (1 << n) - 1) {
        ans = min(ans, cur);
        return;
    }
    // 剪枝
    if (cur >= ans) return;
    for (int i = 0; i < n; ++i) {
        if (mask & (1 << i)) continue;
        ll dist = llabs(pos_[i+1] - pos_[p]);
        // 路上亮灯燃烧：所有未关的灯（包括目标灯自己）烧 dist 秒
        ll burn = 0;
        for (int j = 0; j < n; ++j)
            if (!(mask & (1 << j))) burn += w[j+1];
        ll ncur = cur + burn * dist;
        if (ncur >= ans) continue;
        dfs(i + 1, mask | (1 << i), ncur);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> c;
    for (int i = 1; i <= n; ++i) cin >> pos_[i] >> w[i];
    ans = LLONG_MAX;
    dfs(c, 1 << (c - 1), 0); // 起点的灯先关掉，不烧电
    cout << ans << "\n";
    return 0;
}

复杂度与瓶颈

状态数 $O(n \cdot 2^n)$ ，每个状态 $O(n)$ 个转移、每次转移 $O(n)$ 统计燃烧，总 $O(2^n \cdot n^3)$ ，实测 $n=8$ 内瞬间出解。

瓶颈

瓶颈在于把「已关灯集合」当成任意 $2^n$ 个子集。若集合有结构，状态数可以指数级下降——这正是正解要找的结构。

正解

关键观察：已关灯永远是含 $c$ 的连续区间

adblock: 为什么要「记录停在左/右端」？

反例：假设只记 $f[l][r]$ = 关掉 $[l,r]$ 的最小耗电。考虑样例，关完 $[2,4]$ 后人可能停在 $2$ ，也可能停在 $4$ ：

停在 $4$ 时，下一步去关 $5$ 只需走 $2$ 米；

停在 $2$ 时，去关 $5$ 要走 $6$ 米。

两种停点的耗电不同，且决定后续所有决策的代价。区间耗电的最小值混合了两种停点，无法直接转移——就像「最短路上的点」不能只记终点。因此必须把「人停在哪」也压进状态。又因为从区间内出发，下一步只可能去关紧邻区间的灯（ $l-1$ 或 $r+1$ ，更远的灯必先路过前者），停点只会是 $l$ 或 $r$ 两个端点，所以一维 0/1 就够。

观察 1（路过即关）：若最优路线路过某盏灯而没关它，之后折返再关只会让这盏灯多烧电、且走过的路程不比原路线短——把「关灯」这个动作提前到路过的那一刻，后续状态不变、耗电只减不增。所以存在最优解满足：每盏灯在第一次被路过时就被关掉。

观察 2：人从 $c$ 出发，每步走到相邻未关灯上，于是已关灯集合恰是从 $c$ 向左右两侧连续生长的区间 $[l,r]$ ，且 $l \le c \le r$ 。这就把 $2^n$ 个集合压成 $O(n^2)$ 个区间。

记 $T = \sum w_i$ ，则关 $[l,r]$ 时区间外仍亮的功率和为

W_{out}(a,b) = T - \sum_{i=a}^{b} w_i

用前缀和 $O(1)$ 计算。

思路（区间 DP）

状态定义：

f[l][r][0/1] = \text{关掉 } [l,r] \text{ 内全部灯、人站在 } l\,(0) \text{ 或 } r\,(1) \text{ 时，最小的已发生耗电}

注意语义是「区间外还亮着」，耗电量只统计到此刻为止——区间外灯后续的燃烧会在下一次转移里按步行时长结算。

转移（长度从小到大）：

站到左端 $l$ ：上一步区间是 $[l+1, r]$ ，要么从 $l+1$ 走 $pos_{l+1}-pos_l$ ，要么从 $r$ 走 $pos_r-pos_l$ 。这段路里亮着的灯是 $[l+1,r]$ 外的全部（即 $W_{out}(l+1, r)$ ）：

f[l][r][0] = \min\begin{cases} f[l+1][r][0] + (pos_{l+1}-pos_l)\cdot W_{out}(l+1,r) \\ f[l+1][r][1] + (pos_r-pos_l)\cdot W_{out}(l+1,r) \end{cases}

站到右端 $r$ ：对称地来自 $[l, r-1]$ ，亮灯功率为 $W_{out}(l, r-1)$ ：

f[l][r][1] = \min\begin{cases} f[l][r-1][1] + (pos_r-pos_{r-1})\cdot W_{out}(l,r-1) \\ f[l][r-1][0] + (pos_r-pos_l)\cdot W_{out}(l,r-1) \end{cases}

合法性与初值：只有 $l \le c \le r$ 的状态合法， $f[c][c][0] = f[c][c][1] = 0$ （起点灯免费关掉，之后才开始计时）。

答案： $\min(f[1][n][0],\ f[1][n][1])$ ——关完全部灯，最后停在区间哪端都行。

样例 DP 推演（ $n=5, c=3$ ，各灯： $(2,10)(3,20)(5,20)(6,30)(8,10)$ ， $T=90$ ；数值全部来自程序实测，INF 表示不含 $c$ 的非法状态）：

区间 $[l,r]$	停左端 $f[l][r][0]$	停右端 $f[l][r][1]$	计算说明
$[3,3]$	$0$	$0$	初值：起点灯免费关掉，之后才开始计时
$[2,3]$	$140$	INF	停左： $f[3][3][0]+(5-3)\times W_{out}(3,3)=0+2\times70$ ；停右需 $[2,2]$ 含 $c$ ，非法
$[3,4]$	INF	$70$	停右： $f[3][3][0]+(6-5)\times W_{out}(3,3)=0+1\times70$ ；停左需 $[4,4]$ ，非法
$[2,4]$	$190$	$290$	停左： $f[3][4][1]+(6-3)\times W_{out}(3,4)=70+3\times40$ ；停右： $f[2][3][0]+(6-3)\times W_{out}(2,3)=140+3\times50$
$[3,5]$	INF	$150$	停右： $f[3][4][1]+(8-6)\times W_{out}(3,4)=70+2\times40$ ；停左需 $[4,5]$ ，非法
$[1,4]$	$210$	$350$	停左： $f[2][4][0]+(3-2)\times W_{out}(2,4)=190+1\times20$ （另一来源 $290+4\times20=370$ 劣）；停右： $f[1][3][0]+(6-2)\times W_{out}(1,3)=190+4\times40$
$[2,5]$	$300$	$290$	停左： $f[3][5][1]+(8-3)\times W_{out}(3,5)=150+5\times30$ ；停右： $f[2][4][0]+(8-3)\times W_{out}(2,4)=190+5\times20$ （另一来源 $290+2\times20=330$ 劣）
$[1,5]$	$310$	$270$	停左： $f[2][5][0]+(3-2)\times W_{out}(2,5)=300+1\times10$ （另一来源 $290+6\times10=350$ 劣）；停右： $f[1][4][0]+(8-2)\times W_{out}(1,4)=210+6\times10$ （另一来源 $350+2\times10=370$ 劣）

答案 $\min(f[1][5][0], f[1][5][1]) = \min(310, 270) = 270$ ，对应的最优路线是 3 4 2 1 5：先向右关 $4$ ，回头关 $2,1$ ，最后去关 $5$ ——适当回头正是比「先关完一边再关另一边」更省的关键，与样例解释一致。此表已用程序打印 DP 表逐项核对，并用 $n\le 8$ 的 300 组随机数据与「无任何区间假设」的搜索暴力对拍全部一致。

易错点

必须约束 $l \le c \le r$ ：不含 $c$ 的状态在题目语义下不可达，若不判掉，转移可能从非法状态传染出错误答案。
转移的燃烧对象是区间外：从 $[l+1,r]$ 扩到 $l$ 时，路上烧的是 $W_{out}(l+1,r)$ ，不是 $W_{out}(l,r)$ —— $l$ 这盏灯是走到才关的，它在到达前还在亮。这是本转移最容易写错的一处。
不要写成「区间外未关」的展开式（即把状态理解成「只剩 $[l,r]$ 没关」）：那样转移会把已关灯也计入燃烧，或者漏掉 $c \in [l,r]$ 的约束，推出来的方程在样例上都对不上。
耗电上限约 $50 \times 100 \times (100 \times 100) = 5\times 10^7$ ，int 其实够，但用 long long 更稳妥。
关灯顺序不影响「路过即关」的正确性前提：位置单调递增保证了相邻未关灯必是 $l-1$ / $r+1$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * P1220 关路灯：区间 DP，O(n^2)
 * 状态：f[l][r][0/1] = 已关掉 [l,r] 内所有灯，站在 l 端(0) / r 端(1) 时的最小耗电。
 * 前提：路过某盏灯时顺手关掉一定不亏，所以已关灯永远是包含 c 的连续区间。
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 55;
int n, c;
ll pos_[maxn];   // 灯的位置
ll w[maxn];      // 灯的功率
ll pre[maxn];    // 功率前缀和
ll f[maxn][maxn][2]; // 0: 在左端, 1: 在右端

// [a,b] 外的灯的总功率（这些灯还亮着，走路时每秒烧这么多）
ll Wout(int a, int b) {
    return pre[n] - (pre[b] - pre[a-1]);
}

void read_data() {
    cin >> n >> c;
    for (int i = 1; i <= n; ++i) {
        cin >> pos_[i] >> w[i];
        pre[i] = pre[i-1] + w[i];
    }
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    read_data();

    const ll INF = 0x3f3f3f3f3f3f3f3fLL;
    memset(f, 0x3f, sizeof(f));
    f[c][c][0] = 0;
    f[c][c][1] = 0;

    // 按区间长度从小到大
    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            if (c < l || c > r) continue; // 必须包含起点 c

            // 从 [l+1, r] 走到 l
            ll t = pos_[l+1] - pos_[l];
            f[l][r][0] = min(f[l+1][r][0] + t * Wout(l+1, r),
                             f[l+1][r][1] + (pos_[r] - pos_[l]) * Wout(l+1, r));

            // 从 [l, r-1] 走到 r
            t = pos_[r] - pos_[r-1];
            f[l][r][1] = min(f[l][r-1][1] + t * Wout(l, r-1),
                             f[l][r-1][0] + (pos_[r] - pos_[l]) * Wout(l, r-1));
        }
    }

    cout << min(f[1][n][0], f[1][n][1]) << "\n";
    return 0;
}

复杂度

状态数 $O(n^2)$ ，每个状态 $O(1)$ 转移，总时间 $O(n^2)$ ，空间 $O(n^2)$ 。
$n \le 50$ 下远低于限制；事实上该算法对 $n \le 10^4$ 都能轻松通过。

总结

「路过即关、只减不增」是本题的钥匙：它把任意关灯集合压成含 $c$ 的连续区间 $[l,r]$ ，使状态数从指数降到平方。
区间 DP 的状态除了区间本身，还必须记录决策者停在哪一端：耗电的历史值相同、停点不同，后续代价完全不同——这是「状态必须刻画所有影响未来的信息」的经典体现。
转移时结算的是这段步行时间里仍在亮的灯的功率和：扩展到左端用 $W_{out}(l+1,r)$ ，扩展到右端用 $W_{out}(l,r-1)$ ，新纳入的灯到达瞬间才关。
验证手段上，一个不依赖区间假设的 $O(2^n n^3)$ 暴力搜索是与区间 DP 对拍的黄金标准：两者一致，说明「连续区间」这一结构观察本身就是对的。

目录