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;

  
 

  
1
  
2
 

显然对于每一个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
  
2
  
3
 

最后，因为我们不知道是在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;
}

  
 

  
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
 

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/120810818