洛谷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;
       
       
}
      
      
      
      

       
       
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.