Luogu-P1220-关路灯

Posted on Edited on Word count in article: 845

题目 P1220 关路灯

题目描述

某一村庄在一条路线上安装了 nn 盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。

为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。

现在已知老张走的速度为 1m/s1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，单位：mm）、功率（WW），老张关灯所用的时间很短而可以忽略不计。

请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。

输入格式

第一行是两个数字 nn（表示路灯的总数）和 cc（老张所处位置的路灯号）；

接下来 nn 行，每行两个数据，表示第 11 盏到第 nn 盏路灯的位置和功率。数据保证路灯位置单调递增。

输出格式

一个数据，即最少的功耗（单位：JJ，1J=1W×s1J=1W\times s）。

思路：区间dp

和上一题好像啊！

注意：本题需要分清功和功率两个词。

由于使用了vector数组，所以若无特殊注明，下标均从 0\bold{0} 开始。

基本定义

设 dp[i][j][0/1]dp[i][j][0/1] 表示关掉第 i∼ji \sim j 个灯泡，并且终点在 i/ji/j 的最小电功。

设 pos[x]pos[x] 表示第 xx 个灯泡的位置。

设 rest[i][j]rest[i][j] 表示区间 [i,j]\bold{[i,j]} 外所有灯泡的电功率。

状态

  • 初状态：起点的灯可以瞬间关掉。

    1
    2
    dp[c][c][0] = 0;
    dp[c][c][1] = 0;

  • 状态转移方程：

    对区间 [i,j][i,j]，可以从以下状态转移：

    • 已经关掉了 [i+1,j][i+1,j] 内的灯泡。
    • 已经关掉了 [i,j−1][i,j-1] 内的灯泡。

    以第一种为例，如果终点在 i−1i-1，那么想要去 ii，需要的时间为 i−1i-1 与 ii 的距离（pos[i]−pos[i−1]pos[i]-pos[i-1]），消耗的电功为时间乘亮起灯泡的总电功率（rest[i−1][i]rest[i-1][i]）。其余情况同理。

    因此，状态转移方程如下：

    1
    2
    3
    4
    5
    6
    7
    8
    dp[i][j][0] = min(
      dp[i + 1][j][0] + rest[i + 1][j] * (pos[i + 1] - pos[i]), // (i + 1) -> i
      dp[i + 1][j][1] + rest[i + 1][j] * (pos[j] - pos[i]) // j -> i
    );
    dp[i][j][1] = min(
      dp[i][j - 1][0] + rest[i][j - 1] * (pos[j] - pos[i]), // i -> j
      dp[i][j - 1][1] + rest[i][j - 1] * (pos[j] - pos[j - 1]) // (j - 1) -> j
    );

  • 末状态：关掉所有灯泡消耗的总电功。

    注意：由于不确定终点在左边还是右边更划算，所以需要取最小值。

    1
    ans = min(dp[0][n - 1][0], dp[0][n - 1][1]);

AC Code

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// template v7
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

inline void minset(int &t, int other) {
    t = min(t, other);
}

const int inf = 0x7f7f7f7f;

const int N = 60;

int sum[N];

int rest[N][N];

int dp[N][N][2];

vector<int> pos;

int n, c;

int main() {

    cin >> n >> c;
    c--;
    int t1, t2;
    for(int i = 1; i <= n; i++) {
        cin >> t1 >> t2;
        pos.push_back(t1);
        sum[i] = t2 + sum[i - 1];
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            rest[i][j] = sum[n] - sum[j + 1] + sum[i];
            // index 0 1 2 3 4 5 6 7 8 -> n
            // pos   0 1 2 4 5 7 8 9
            // power 1 1 1 1 1 1 1 1
            // sum   0 1 2 3 4 5 6 7 8
            // rest[3][6] = sum[n] - sum[j + 1] + sum[i]
        }
    }
    memset(dp, inf, sizeof dp);
    dp[c][c][0] = 0;
    dp[c][c][1] = 0;
    // dp[i][j][s]: start with s, [i, j]
    for(int len = 1; len < n; len++)
        for(int i = 0; i < n - len; i++){
            int j = i + len;
            // [i, j] <- [i + 1, j] / [i, j - 1]
            dp[i][j][0] = min(
                dp[i + 1][j][0] + rest[i + 1][j] * (pos[i + 1] - pos[i]), // (i + 1) -> i
                dp[i + 1][j][1] + rest[i + 1][j] * (pos[j] - pos[i]) // j -> i 190
            );
            dp[i][j][1] = min(
                dp[i][j - 1][0] + rest[i][j - 1] * (pos[j] - pos[i]), // i -> j
                dp[i][j - 1][1] + rest[i][j - 1] * (pos[j] - pos[j - 1]) // (j - 1) -> j
            );
        }
    cout << min(dp[0][n - 1][0], dp[0][n - 1][1]) << endl;
    return 0;
}

补充

为什么第三维不需要枚举每个位置

上述定义中，dpdp 数组只描述了终点在最左端和最右端的情况。

不需要枚举每个位置的原因是，最边上的灯泡一定是最后一个关闭的，否则一定不是最优解。