洛谷题单指南-动态规划3-P1220 关路灯

原题链接：https://www.luogu.com.cn/problem/P1220

题意解读：按坐标顺序排列1~n个路灯，每个路灯有不同的功耗，老张从位置c开始关灯，第一时间关掉c位置的灯，每次关掉一个灯之后，可以往右走、也可以往左走关下一个灯，老张速度是1m/s，求所有灯都关掉所消耗的最少功耗。

解题思路：

由题意分析，关闭一个范围内路灯的过程所消耗的功耗，可以由关闭该范围内一部分路灯的消耗推出，大概率是一个区间DP问题。

尝试进行DP问题分析：

1、状态表示

考虑最后一个关闭的路灯，根据题意，最后一个关闭的要么是头，要么是尾，有两种可能

所以预设两个状态：

设f[i][j]表示将第i ~ j的路灯关闭，且最后一个关闭的是i时，所消耗的总功耗；

设g[i][j]表示将第i ~ j的路灯关闭，且最后一个关闭的是j时，所消耗的总功耗；

设a[i]是第i个路灯的坐标，b[i]是第i个路灯的功耗。

2、状态转移

对于f[i][j]，由于最后一个关闭的是i，因此可能有两种情况：从i+1到i、从j到i

  f[i][j] = min(f[i+1][j] + 关最后一个路灯的时间内所有亮着的灯的功耗，g[i+1][j] + 关最后一个路灯的时间内所有亮着的灯的功耗)

  对于情况一：f[i+1][j] + 关最后一个路灯的时间所有亮着的灯的功耗

    如何计算“关最后一个路灯的时间内所有亮着的灯的功耗”？

    如上图，最后一步，老张从i+1到i，所需时间为a[i+1] - a[i]，此时所有未关闭的灯是1~i、j+1~n，总功耗就是时间 * 这些灯的功耗之和 

    如何求1~i、j+1~n的功耗之和？可以借助前缀和！

    设s[i]是b[1]~b[i]的和，即s[]是b[]的前缀和数组。

    则有“关最后一个路灯的时间内所有亮着的灯的功耗” = (a[i+1] - a[i]) * (s[i] + s[n] - s[j])

  对于情况二：g[i][j-1] + 关最后一个路灯的时间内所有亮着的灯的功耗

    如何计算“关最后一个路灯的时间内所有亮着的灯的功耗”？

    如上图，最后一步，老张从j到i，所需时间为a[j] - a[i]，此时所有未关闭的灯是1~i、j+1~n，总功耗就是时间 * 这些灯的功耗之和 

    则有“关最后一个路灯的时间内所有亮着的灯的功耗” = (a[j] - a[i]) * (s[i] + s[n] - s[j])

所以有

f[i][j] = min(f[i+1][j] + (a[i+1] - a[i]) * (s[i] + s[n] - s[j])，g[i+1][j] + (a[j] - a[i]) * (s[i] + s[n] - s[j]))

同样的方式，可以得到

如上图，对应f[i][j-1] + (a[j] - a[i]) * (s[i-1] + s[n] - s[j-1])

如上图，对应g[i][j-1] + (a[j] - a[j-1]) * (s[i-1] + s[n] - s[j-1])

所以有

g[i][j] = min(f[i][j-1] + (a[j] - a[i]) * (s[i-1] + s[n] - s[j-1]), g[i][j-1] + (a[j] - a[j-1]) * (s[i-1] + s[n] - s[j-1]))

枚举时，可以先枚举区间长度，任何一次关闭动作要从一个路灯走到另一个路灯，区间长度至少是2，再枚举左端点，计算右端点即可。

3、初始化

f、g初始化为极大值，方便求最小值

对于位置c已经瞬间关闭，因此f[c][c] = g[c][c] = 0

4、结果

min ( f[1][n] , g[1][n] )

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N= 55;
int n, c;
int a[N], b[N], s[N]; //a[i]是第i个路灯的坐标，b[i]是第i个路灯的功耗，s是b的前缀和
int f[N][N]; //f[i][j]表示将第i ~ j的路灯关闭，且最后一个关闭的是i时，所消耗的总功耗
int g[N][N]; //g[i][j]表示将第i ~ j的路灯关闭，且最后一个关闭的是j时，所消耗的总功耗

int main()
{
    cin >> n >> c;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
        s[i] = s[i-1] + b[i];
    } 

    memset(f, 0x3f, sizeof(f));
    memset(g, 0x3f, sizeof(g));
    f[c][c] = g[c][c] = 0; //c路灯瞬间关闭，不消耗时间
    for(int len = 2; len <= n; len++)
    {
        for(int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            f[i][j] = min(f[i+1][j] + (a[i+1] - a[i]) * (s[i] + s[n] - s[j]), g[i+1][j] + (a[j] - a[i]) * (s[i] + s[n] - s[j]));
            g[i][j] = min(f[i][j-1] + (a[j] - a[i]) * (s[i-1] + s[n] - s[j-1]), g[i][j-1] + (a[j] - a[j-1]) * (s[i-1] + s[n] - s[j-1]));
        }
    }
    cout << min(f[1][n], g[1][n]);

    return 0;
}