洛谷P1220 关路灯【区间dp】

我就是我 2021-12-12 15:43 278阅读 0赞

**题目**：[https://www.luogu.org/problemnew/show/P1220][https_www.luogu.org_problemnew_show_P1220]

**题意**：给定n盏灯的位置和功率，初始时站在第c盏处。

关灯不需要时间，走的速度是1单位/秒。问把所有的灯关掉，最少功率是多少。

思路：看上去是区间dp还挺清楚的。因为关灯不需要时间，既然路过了就顺便关了吧。所以肯定是中间某一段的灯都被关了，两端各有一段亮着。

所以我们可以用$dp\[i\]\[j\]$表示i~j号灯都被关了。但是最后关的是$i$还是$j$还是有差别的，所以还需要一维来标记。

因为需要区间和，所以再用$sum$维护区间前缀和

最后得到状态转移方程

$dp\[i\]\[j\]\[0\] = min(dp\[i+1\]\[j\]\[0\] + (pos\[i+1\] - pos\[i\]) \* (sum\[i\] + sum\[n\] - sum\[j\]), dp\[i+1\]\[j\]\[1\] + (pos\[j\] - pos\[i\]) \* (sum\[i\] + sum\[n\] - sum\[j\]))$

$dp\[i\]\[j\]\[1\] = min(dp\[i\]\[j-1\]\[1\] + (pos\[j\] - pos\[j - 1\]) \* (sum\[n\] - sum\[j - 1\] + sum\[i - 1\]), dp\[i\]\[j-1\]\[0\] + (pos\[j\] - pos\[i\]) \* (sum\[n\] - sum\[j - 1\] + sum\[i - 1\]))$

要注意两个情况灯的功率是不同的。

初始情况和结束情况都比较好判断。

中间更新的话其实就是枚举关了的灯的数量，然后枚举起点就可以了。

1 #include<cstdio>
     2 #include<cstdlib>
     3 #include<map>
     4 #include<set>
     5 #include<cstring>
     6 #include<algorithm>
     7 #include<vector>
     8 #include<cmath> 
     9 #include<stack>
    10 #include<queue>
    11 #include<iostream>
    12 
    13 #define inf 0x7fffffff
    14 using namespace std;
    15 typedef long long LL;
    16 typedef pair<int, int> pr;
    17 
    18 int n;
    19 const int maxn = 55;
    20 int c;
    21 int light[maxn], sum[maxn], pos[maxn];
    22 int dp[maxn][maxn][2];
    23 
    24 int main()
    25 {
    26     memset(dp, 0x3f, sizeof(dp));
    27     scanf("%d%d", &n, &c);
    28     for(int i = 1; i <= n; i++){
    29         scanf("%d%d", &pos[i], &light[i]);
    30         sum[i] = sum[i - 1] + light[i];
    31     }
    32     dp[c][c][0] = dp[c][c][1] = 0;
    33     for(int num = 2; num <= n; num++){
    34         for(int l = 1; l + num - 1 <= n; l++){
    35             int r = l + num - 1;
    36             int x = sum[l] + sum[n] - sum[r], y = sum[l - 1] + sum[n] - sum[r - 1];
    37             dp[l][r][0] = min(dp[l][r][0], dp[l + 1][r][0] + (pos[l + 1] - pos[l]) * x);
    38             dp[l][r][0] = min(dp[l][r][0], dp[l + 1][r][1] + (pos[r] - pos[l]) * x);
    39             dp[l][r][1] = min(dp[l][r][1], dp[l][r - 1][1] + (pos[r] - pos[r - 1]) * y);
    40             dp[l][r][1] = min(dp[l][r][1], dp[l][r - 1][0] + (pos[r] - pos[l]) * y);
    41         }
    42     }
    43     
    44     printf("%d\n", min(dp[1][n][0], dp[1][n][1]));
    45     
    46 }

转载于:https://www.cnblogs.com/wyboooo/p/11079806.html

[https_www.luogu.org_problemnew_show_P1220]: https://www.luogu.org/problemnew/show/P1220