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

}

巴特西

洛谷P1220 关路灯题解区间DP

最新文章

热门文章

巴特西

洛谷P1220 关路灯 题解 区间DP

最新文章

热门文章

洛谷P1220 关路灯题解区间DP