文章目录

• P1220 关路灯
• AC代码

P1220 关路灯

本题链接：P1220 关路灯

本博客给出本题截图：

AC代码

代码解释：

这个题整体来看还是比较好想的，下面我们一步一步去分析这个问题：

首先我们去想这个题可以怎么去做，这里有三种思路

①dfs + 玄学剪枝

②贪心

③动态规划

这里我们来说第三种做法 （第一种第二种还没想过怎么代码实践

首先，不管我们怎么去写这个dp，都有一个我们绕不开的东西：我们需要不断的去计算消耗电量这个问题，这个其实就是时间(路程)×功率，这个是是根据时间的消耗是不断累加的，然后又因为dp的本质其实是最优选法的暴力，所以对于每一个不同的状态，如果我们都要去不断的叠加这个耗电量的话，很可能会TLE，那么对于处理这样的有反复计算叠加的问题，显然我们可以用 前缀和 的思维去进行优化.

好了，说完这一点，我们来看这个dp的具体实现部分 (敲黑板！

这么一个区间的问题，最简单的考虑方式就是由一个二维数组f[i][j]去表示，这个数组所表达的含义为[i, j]这一段的路灯已经全部熄灭的耗电量的最少值，即只有[1 ~ i)和(j, n]上的灯是处于点亮的状态时，当前的耗电量最小值

我们在定义到现在，需不需要再补充点什么东西呢？显然是需要的，我们虽然按照如上的方式去定义了f[i][j]，但是，我们却不知道我们所处在哪个位置，即我们虽然保证了[i, j]上的所有灯都是处于熄灭的状态，但是我们却不知道我们现在在哪个位置，因为位置是决定时间的，而时间是决定耗电量的关键，故我们还需要规定一下我们的位置，显然，我们只可能处在i这个点上或者j这个点上，故我们不妨去规定f[i][j][0]代表[i, j]之间所有的灯都处于熄灭的状态且我们站在i这个点，f[i][j][1]代表[i, j]之间所有的灯都处于熄灭的状态且我们站在j这个点

以上，就是我们的dp方程的定义，下面，也是最难的，如何去写这个状态转移方程：

有初始化：

memset(f, 0x3f, sizeof f);
f[c][c][0] = f[c][c][1] = 0;

显然对于每一个f[i][j]，我们都要去分两个方面去思考状态转移方程：即分别去计算f[i][j][0]和f[i][j][1]的min，下面去介绍如何计算：

对于f[i][j][0]这个点，我们只可能从f[i + 1][j]转移而来，即f[i][j][0] = min(f[i + 1][j][0] + num1, f[i + 1][j][1] + num2);,其中num1和num2分别指从f[i + 1][j][0]和f[i + 1][j][1] 转移到f[i][j][0]的过程中，其余灯泡的耗电量

在本题解的最开头已经说明利用 前缀和 的思维去进行优化，这里来说具体时间，我们的p数组就是前缀和数组，d数组代表的是我们的距离数组，那么我们在从i + 1移动到i的这个过程中消耗的时间（即路程）分别为：d[i + 1] - d[i]，d[j] - d[i],那么在这两个过程中哪些灯泡是正在处于点亮耗电状态呢：p[i] + p[n] - p[j]，（对这一步有疑问的话可以去模拟一下例子），f[i][j][1]的转移方法和f[i][j][0]一致，这里不再过多赘述，读者可以自己写一下，和我的代码进行对比即可

那么剩下的就是迈向成功的最后一步：如何去写for循环

因为在c处的灯是瞬间熄灭的，所以熄灭灯的长度最少是从2开始的，且不能超过n，然后开始枚举左端点即可，利用l(长度)和i(左端点)可以计算出右端点，即：

for (int l = 2; l <= n; l ++ )
    for (int i = 1; i + l - 1 <= n; i ++ )
      int j = i + l - 1;

最后，因为我们不知道是在1处有最小值还是在n处有最小值，故直接对f[1][n][0]和f[1][n][1]取最小值即可

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 55;
int n, c;
int f[N][N][2];
int p[N], d[N];
int main()
{
  int n, c;
  cin >> n >> c;
  for (int i = 1; i <= n; i ++ )
  {
    int w;
    cin >> d[i] >> w;
    p[i] = p[i - 1] + w;
  }
  memset(f, 0x3f, sizeof f);
  f[c][c][0] = f[c][c][1] = 0;
  for (int l = 2; l <= n; l ++ )
    for (int i = 1; i + l - 1 <= n; i ++ )
    {
      int j = i + l - 1;
      f[i][j][0] = min(f[i + 1][j][0] + (d[i + 1] - d[i]) * (p[i] + p[n] - p[j]), f[i + 1][j][1] + (d[j] - d[i]) * (p[i] + p[n] - p[j]));
      f[i][j][1] = min(f[i][j - 1][0] + (d[j] - d[i]) * (p[i - 1] + p[n] - p[j - 1]), f[i][j - 1][1] + (d[j] - d[j - 1]) * (p[i - 1] + p[n] - p[j - 1]));
    }
  cout << min(f[1][n][0], f[1][n][1]) << endl;
  return 0;
}