洛谷P1220 关路灯【区间dp】

题目：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]))$

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

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

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

 #include<cstdio>

 #include<cstdlib>

 #include<map>

 #include<set>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<stack>

 #include<queue>

 #include<iostream>

 #define inf 0x7fffffff

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> pr;

 int n;

 const int maxn = ;

 int c;

 int light[maxn], sum[maxn], pos[maxn];

 int dp[maxn][maxn][];

 int main()

 {

     memset(dp, 0x3f, sizeof(dp));

     scanf("%d%d", &n, &c);

     for(int i = ; i <= n; i++){

         scanf("%d%d", &pos[i], &light[i]);

         sum[i] = sum[i - ] + light[i];

     }

     dp[c][c][] = dp[c][c][] = ;

     for(int num = ; num <= n; num++){

         for(int l = ; l + num -  <= n; l++){

             int r = l + num - ;

             int x = sum[l] + sum[n] - sum[r], y = sum[l - ] + sum[n] - sum[r - ];

             dp[l][r][] = min(dp[l][r][], dp[l + ][r][] + (pos[l + ] - pos[l]) * x);

             dp[l][r][] = min(dp[l][r][], dp[l + ][r][] + (pos[r] - pos[l]) * x);

             dp[l][r][] = min(dp[l][r][], dp[l][r - ][] + (pos[r] - pos[r - ]) * y);

             dp[l][r][] = min(dp[l][r][], dp[l][r - ][] + (pos[r] - pos[l]) * y);

         }

     }

     printf("%d\n", min(dp[][n][], dp[][n][]));

 }

巴特西

洛谷P1220 关路灯【区间dp】

最新文章

热门文章