洛谷P1220 关路灯 题解 区间DP

题目链接：https://www.luogu.com.cn/problem/P1220

本题涉及算法：区间DP。

我们一开始要做一些初始化操作，令：

• \(p[i]\) 表示第i个路灯的位置；
• \(w[i]\) 表示第i个路灯的功率；
• \(sum[i]\) 表示前i个路灯的总功率

我们设状态 \(f[l][r][i]\) 表示：

• 当 \(i=0\) 时，老张关了编号 \([l,r]\) 范围内的所有灯，并且此时老张在第 \(l\) 盏灯处（最左边）的最少消耗电量；
• 当 \(i=1\) 时，老张关了编号\([l,r]\) 范围内的所有灯，并且此时老张在第 \(r\) 盏灯处（最右边）的最少消耗电量。

则我们可以得出状态转移方程如下：

\[f[l][r][0] = min(f[l+1][r][0] + (sum[l] + sum[n] - sum[r]) * (p[l+1] - p[l]), f[l+1][r][1] + (sum[l] + sum[n] - sum[r]) * (p[r] - p[l])) \]

\[f[l][r][1] = min(f[l][r-1][0] + (sum[l-1] + sum[n] - sum[r-1]) * (p[r] - p[l]),f[l][r-1][1] + (sum[l-1] + sum[n] - sum[r-1]) * (p[r] - p[r-1])) \]

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
int n, c;
long long p[maxn],  // p[i]表示第i个路灯的位置
    w[maxn],        // w[i]表示第i个路灯的功率
    sum[maxn],      // sum[i]表示前i个路灯的总功率
    f[maxn][maxn][2];  // f[l][r][0]表示关了[l,r]范围内的灯并且当前在l位置的最小功率；
                        // f[l][r][1]表示关了[l,r]范围内的灯并且当前在r位置的最小功率
const long long INF = (1LL<<60);
int main() {
    cin >> n >> c;
    for (int i = 1; i <= n; i ++) {
        cin >> p[i] >> w[i];
        sum[i] = sum[i-1] + w[i];
    }
    for (int i = 1; i <= n; i ++)
        for (int j = i; j <= n; j ++)
            f[i][j][0] = f[i][j][1] = INF;
    f[c][c][0] = f[c][c][1] = 0;    // 一开始在第c盏路灯不消耗电量
    for (int len = 2; len <= n; len ++) {
        for (int l = max(1, c-len+1); l+len-1 <= n; l ++) {
            int r = l+len-1;
            f[l][r][0] = min(f[l+1][r][0] + (sum[l] + sum[n] - sum[r]) * (p[l+1] - p[l]),
                             f[l+1][r][1] + (sum[l] + sum[n] - sum[r]) * (p[r] - p[l]));
            f[l][r][1] = min(f[l][r-1][0] + (sum[l-1] + sum[n] - sum[r-1]) * (p[r] - p[l]),
                             f[l][r-1][1] + (sum[l-1] + sum[n] - sum[r-1]) * (p[r] - p[r-1]));
        }
    }
    cout << min(f[1][n][0], f[1][n][1]) << endl;
    return 0;
}