关路灯（区间dp）

关路灯

题目描述：

有$n$个路灯，形成一排，一开始你在$pos1$的位置，每个路灯都有一个功率$w_i$，你的行进速度为1，问如何关路灯使得所有路灯的总功率最小，输出最小的总耗电量。

数据范围：

$$1\le n\le 50，1\le w_i\le n$$

思路

• 状态：$dp[i][j][0/1]$表示关完区间$[i,j]$之间的所有的路灯在$i$的位置或者在$j$的位置时所有路灯的总消耗。
• 转移：$dp[i][j][0]$可以从$dp[i+1][j][0/1]$转移过去， $dp[i][j][1]$可以从$dp[i][j-1][0/1]$转移过去。
• 转移的时候要加上所有的未关闭的路灯的总功率乘上移动时间。
• 答案就是 $dp[1][n][0/1]取最小值$

代码：

#include 
using namespace std;

const int N = 55;
int f[N][N][2], w[N], pos0, pos[N], n, sum[N];

int main(){
	scanf("%d %d",&n, &pos0);
	for(int i = 1; i <= n; i ++ ){
		scanf("%d %d",&pos[i], &w[i]);
	}
	for(int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + w[i];
	memset(f, 127, sizeof f);
	f[pos0][pos0][0] = f[pos0][pos0][1] = 0;
	for(int i = 2; i <= n; i ++ ){
		for(int j = 1; j + i - 1 <= n; j ++ ){
			int ed = j + i - 1;
			int x = f[j + 1][ed][0] + (pos[j + 1] - pos[j]) * (sum[j] + sum[n] - sum[ed]);
			int y = f[j + 1][ed][1] + (pos[ed] - pos[j]) * (sum[j] + sum[n] - sum[ed]);
			f[j][ed][0] = min(x, y);
			//求f[j][ed][1] 从j - ed - 1转移
			x = f[j][ed - 1][0] + (pos[ed] - pos[j]) * (sum[j - 1] + sum[n] - sum[ed - 1]);
			y = f[j][ed - 1][1] + (pos[ed] - pos[ed - 1]) * (sum[j - 1] + sum[n] - sum[ed - 1]);
			f[j][ed][1] = min(x, y);
		}
	}
	printf("%d", min(f[1][n][0], f[1][n][1]));
	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