P1220 关路灯

P1220 关路灯

▍题意
一条笔直的道路上装有 $n$ 盏路灯，每盏路灯的位置为 $x_i$，功率为 $w_i$。初始时，人物位于第 $c$ 盏路灯处，且该路灯处于开启状态，其余路灯均关闭。每次可以向左或向右移动一单位距离，耗时 $1$ 秒；到达路灯处可立即关闭该灯（不耗时）。移动过程中，所有未关闭的路灯每秒消耗等于其功率的电力。求关闭所有路灯时，最小总电力消耗（仅计算移动过程中消耗的电力）。
数据范围：$1\le n\le 50$，$1\le c\le n$，$0\le x_i\le 1000$（位置单调递增），$1\le w_i\le 100$。

▍分析
动态规划求解。定义 $dp[l][r][0/1]$ 表示已经关闭区间 $[l,r]$ 内所有路灯后，停留在左端点（$0$）或右端点（$1$）时的最小电力消耗。

• 状态转移：从小区间向大区间扩展：
  • $dp[l][r][0]$ 有两种来源：
    • 从 $dp[l+1][r][0]$ 左移到 $l$：消耗时间 $(x_{l+1}-x_l)\times \text{剩余功率和}$
    • 从 $dp[l+1][r][1]$ 左移到 $l$：消耗时间 $(x_r-x_l)\times \text{剩余功率和}$
  • $dp[l][r][1]$ 有两种来源：
    • 从 $dp[l][r-1][0]$ 右移到 $r$：消耗时间 $(x_r-x_l)\times \text{剩余功率和}$
    • 从 $dp[l][r-1][1]$ 右移到 $r$：消耗时间 $(x_r-x_{r-1})\times \text{剩余功率和}$
• 关键优化：

  • 预处理功率前缀和 $sum[i]={\sum }_{k=1}^i{w}_k$。

  • 转移时，剩余功率和为分两种情况：

    • $cost1=sum[n]-(sum[r]-sum[l])$
    • $cost2=sum[n]-(sum[r-1]-sum[l-1])$

    分别表示关闭区间 $[l+1,r]、[l,r-1]$ 的消耗电力总和。

• 初始化：$dp[c][c][0]=dp[c][c][1]=0$（起点无耗时）。
  时间复杂度：$O(n^2)$（区间DP枚举 $l,r$）。

▍参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
/*
动态规划
    状态表示：f[l][r][0/1]
        集合：len=r-l+1,(所有的)关闭区间长度为 len ，且停留在 l/r(0/1) 点的消耗电力方案。
        属性：Min 最小值
    状态计算：
        子集划分：
        - cost1=sum[n]-(sum[r]-sum[l]),cost2=sum[n]-(sum[r-1]-sum[l-1])，分别表示关闭区间[l+1,r]、[l,r-1]的消耗电力总和。
        - 分 2 大类，4 种情况进行转移
        类型 1：停留在 l 左端点的方案，取最小值Min( 1),2) )。
            1) f[l][r][0], [l,r]<-[(l+1),r], time=x[l+1]-x[l],总消耗功率：time*cost, f[l][r][0]=f[l+1][r][0] + time*cost;
            2) f[l][r][0], [l,r]<-[l+1,(r)], time=x[r]-x[l],总消耗功率：time*cost, f[l][r][0]=f[l+1][r][1] + time*cost;
        类型 2：停留在 r 右端点的方案，取最小值Min( 3),4) )。
            3) f[l][r][1], [(l),r-1]->[l,r], time=x[r]-x[l],总消耗功率：times*cost, f[l][r][1]=f[l][r-1][0] + times*cost;
            4) f[l][r][1], [l,r-1]->[l,r], time=x[r]-x[r-1],总消耗功率：times*cost, f[l][r][1]=f[l][r-1][1] + times*cost;
    最终答案：
        ans = min( f[1][n][0], f[1][n][1] )，关闭长度为 n 的区间，最终可能落位在左端点 1 或者右端点 n 的消耗方案。
*/
const int N = 55;
int n, c;
int x[N], f[N][N][2], sum[N], w[N];

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> c;
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i] >> w[i];
        sum[i] = sum[i - 1] + w[i];
    }
    /* dp求最小，初始化最大 */
    memset(f, 0x3f, sizeof f);
    /* 初始化：开始所在位置的消耗为 0 */
    f[c][c][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;
            int cost1 = sum[n] - (sum[r] - sum[l]);                                                                                /* 区间[l+1,r]消耗的功率之和 */
            int cost2 = sum[n] - (sum[r - 1] - sum[l - 1]);                                                                        /* 区间[l,r-1]消耗的功率之和 */
            f[l][r][0] = min(f[l][r][0], min(f[l + 1][r][0] + cost1 * (x[l + 1] - x[l]), f[l + 1][r][1] + cost1 * (x[r] - x[l]))); /* 类型 1) */
            f[l][r][1] = min(f[l][r][1], min(f[l][r - 1][0] + cost2 * (x[r] - x[l]), f[l][r - 1][1] + cost2 * (x[r] - x[r - 1]))); /* 类型 2) */
        }
    }
    cout << min(f[1][n][0], f[1][n][1]) << "\n";
    return 0;
}