1. 问题特点

有些题目的操作过程始终围绕一个已经处理的连续区间进行：每次从当前区间向左或向右扩展一个位置。只记录区间 $[l,r]$ 还不够，因为下一步的代价还取决于当前人或物体位于区间的哪一端。

这类题通常增加一个端点状态：

$$dp[l][r][0/1]$$

其中 $0$ 和 $1$ 分别表示当前位于区间左端或右端。典型题目包括关路灯、邮局配送等。

2. 例题：P1220 关路灯

1. 题目描述

一条路上有 $n$ 盏路灯，从左到右排列。第 $i$ 盏路灯的位置为 $x_i$，功率为 $w_i$。起初所有路灯都亮着，工作人员从第 $c$ 盏路灯的位置出发，关闭全部路灯。

工作人员每秒可以沿道路移动一个单位距离。某段时间内还亮着的路灯会持续耗电，耗电功率等于所有亮着路灯的功率之和。求关闭所有路灯所需的最小总耗电量。

第一行输入 $n$ 和 $c$。接下来 $n$ 行，每行输入一盏灯的位置 $x_i$ 和功率 $w_i$，位置按从左到右递增。题目范围为 $n\le50$。

例如，下面的数据对应的最小耗电量为 $29$：

4 3
1 2
2 3
5 4
6 2

2. 观察操作顺序

设已经关闭的路灯编号构成区间 $[l,r]$，并且该区间包含起点 $c$。由于从 $c$ 出发，每次关闭当前已关闭区间左边或右边紧邻的一盏灯，所以已关闭的路灯始终构成一个连续区间。

接下来只能向左关闭第 $l-1$ 盏灯，或者向右关闭第 $r+1$ 盏灯。要计算移动代价，还必须知道工作人员当前站在 $x_l$ 还是 $x_r$，因此状态需要记录位置端点。

3. 状态定义

定义：

$$dp[l][r][0]=\text{关闭区间 }[l,r]\text{ 后，工作人员位于 }x_l\text{ 时的最小耗电量}$$$$dp[l][r][1]=\text{关闭区间 }[l,r]\text{ 后，工作人员位于 }x_r\text{ 时的最小耗电量}$$

状态只考虑包含出发点 $c$ 的区间。开始时只关闭第 $c$ 盏灯，工作人员就在 $x_c$：

$$dp[c][c][0]=dp[c][c][1]=0$$

4. 计算一次扩展的耗电量

设所有路灯功率之和为 $W$，前缀和为 $prefix$。关闭区间 $[l,r]$ 后，仍亮着的路灯总功率为：

$$remain=W-(prefix[r]-prefix[l-1])$$

如果移动距离为 $d$，移动期间的耗电量就是：

$$d\times remain$$

注意，移动过程中还没有关闭下一盏灯，因此这段路程按当前仍亮着的路灯功率计算。

5. 状态转移

从区间 $[l,r]$ 向左扩展到 $[l-1,r]$ 时：

$$dp[l-1][r][0]=\min\begin{cases} dp[l][r][0]+(x_l-x_{l-1})\times remain\\ dp[l][r][1]+(x_r-x_{l-1})\times remain \end{cases}$$

从区间 $[l,r]$ 向右扩展到 $[l,r+1]$ 时：

$$dp[l][r+1][1]=\min\begin{cases} dp[l][r][0]+(x_{r+1}-x_l)\times remain\\ dp[l][r][1]+(x_{r+1}-x_r)\times remain \end{cases}$$

向左扩展后人位于新区间左端 $x_{l-1}$；向右扩展后人位于新区间右端 $x_{r+1}$。每次扩展都会使区间长度增加 $1$，所以按区间长度从小到大计算。

6. C++ 实现

#include <algorithm>
#include <iostream>
using namespace std;

const int MAXN = 55;
const long long INF = (1LL << 60);

int position[MAXN];
long long powerValue[MAXN];
long long prefix[MAXN];
long long dp[MAXN][MAXN][2];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, c;
    cin >> n >> c;
    for (int i = 1; i <= n; ++i) {
        cin >> position[i] >> powerValue[i];
        prefix[i] = prefix[i - 1] + powerValue[i];
    }

    for (int l = 1; l <= n; ++l) {
        for (int r = 1; r <= n; ++r) {
            dp[l][r][0] = INF;
            dp[l][r][1] = INF;
        }
    }
    dp[c][c][0] = 0;
    dp[c][c][1] = 0;

    for (int len = 1; len <= n; ++len) {
        int leftMin = max(1, c - len + 1);
        int leftMax = min(c, n - len + 1);

        for (int l = leftMin; l <= leftMax; ++l) {
            int r = l + len - 1;
            long long remain = prefix[n] - (prefix[r] - prefix[l - 1]);

            if (l > 1) {
                dp[l - 1][r][0] = min(
                    dp[l - 1][r][0],
                    dp[l][r][0] + 1LL * (position[l] - position[l - 1]) * remain
                );
                dp[l - 1][r][0] = min(
                    dp[l - 1][r][0],
                    dp[l][r][1] + 1LL * (position[r] - position[l - 1]) * remain
                );
            }

            if (r < n) {
                dp[l][r + 1][1] = min(
                    dp[l][r + 1][1],
                    dp[l][r][0] + 1LL * (position[r + 1] - position[l]) * remain
                );
                dp[l][r + 1][1] = min(
                    dp[l][r + 1][1],
                    dp[l][r][1] + 1LL * (position[r + 1] - position[r]) * remain
                );
            }
        }
    }

    cout << min(dp[1][n][0], dp[1][n][1]) << '\n';
    return 0;
}

循环只枚举包含 $c$ 的区间。先处理长度为 $1$ 的状态，再逐步扩展；这样更新到的长度为 $len+1$ 的状态会在之后被处理。

区间共有 $O(n^2)$ 个，每个状态只尝试向左、向右扩展，因此时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。