洛谷P1220 关路灯

题目描述

某一村庄在一条路线上安装了 \(n\) 盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。

为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。

现在已知老张走的速度为 \(1m/s\)，每个路灯的位置（是一个整数，即距路线起点的距离，单位：\(m\)）、功率（\(W\)），老张关灯所用的时间很短而可以忽略不计。

请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。

输入格式

第一行是两个数字 \(n\)（表示路灯的总数）和 \(c\)（老张所处位置的路灯号）；

接下来 \(n\) 行，每行两个数据，表示第 \(1\) 盏到第 \(n\) 盏路灯的位置和功率。数据保证路灯位置单调递增。

输出格式

一个数据，即最少的功耗（单位：\(J\)，\(1J=1W\times s\)）。

样例 #1

样例输入 #1

5 3
2 10
3 20
5 20
6 30
8 10

样例输出 #1

270

提示

样例解释

此时关灯顺序为 3 4 2 1 5。

数据范围

\(1\le n\le50\)，\(1\le c\le n\)。

思路

一道区间动态规划题目，枚举区间长度和区间左右端点。
首先预处理出耗电功率的前缀和。

• 状态表示：\(f[l][r]\) 表示关掉 \(a[l]\) 到 \(a[r]\) 的所有灯的方案。此外该题目提到老张关灯可以左右方向改变，那么我们就要考虑老张最后关掉的灯是哪一个端点，\(f[l][r][0]\) 表示最后老张在左端点，即 \(a[l]\) 处，\(f[l][r][1]\) 表示最后老张在右端点，即 \(a[r]\) 处。
• 状态计算：如果最后关掉的灯是左端点的，那么 \(f[l][r][0]\)，老张将 \(a[l+1]\) 至 \(a[r]\) 的所有灯都关掉了，那么老张要么是在 \(a[l+1]\) 处，要么是在 \(a[r]\) 处，因此状态转移方程为 \(f[l][r][0]=min(f[l+1][r][0]+(a[l+1]-a[l]) * (s[l]+s[n]-s[r]),f[l+1][r][1]+(a[r]-a[l]) * (s[l]+s[n]-s[r]))\)；如果最后关掉的灯是右端点的，那么 \(f[l][r][1]\)，老张将 \(a[l]\) 至 \(a[r-1]\) 的所有灯都关掉了，那么老张要么是在 \(a[l]\) 处，要么是在 \(a[r-1]\) 处，因此状态转移方程为 \(f[l][r][1]=min(f[l][r-1][0]+(a[r]-a[l]) * (s[l-1]+s[n]-s[r-1]),f[l][r-1][1]+(a[r]-a[r-1]) * (s[l-1]+s[n]-s[r-1]))\)。

C++代码

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
typedef pair<int, int> PII;
typedef long long LL;

int n, c;
int a[N], b[N];
int s[N], f[N][N][2]; // f[i][j] 表示将i到j位置的灯关掉的方案

int main ()
{
	scanf("%d%d", &n, &c);
	for (int i = 1; i <= n; i ++)
		scanf("%d%d", &a[i], &b[i]);
	for (int i = 1; i <= n; i ++)
		s[i] = s[i - 1] + b[i];
	memset(f, 0x3f, sizeof f);
	f[c][c][0] = f[c][c][1] = 0;
	for (int len = 2; len <= n; len ++)
		for (int i = 1; i + len - 1 <= n; i ++)
		{
			int l = i, r = i + len - 1;
			// 0 最后在l处 此处灯最后关其余灯都关了
			f[l][r][0] = min(f[l + 1][r][0] + (a[l + 1] - a[l]) * (s[l] + s[n] - s[r]),
				f[l + 1][r][1] + (a[r] - a[l]) * (s[l] + s[n] - s[r]));
			// 1 最后在r处 此处灯最后关其余灯都关了
			f[l][r][1] = min(f[l][r - 1][0] + (a[r] - a[l]) * (s[l - 1] + s[n] - s[r - 1]),
				f[l][r - 1][1] + (a[r] - a[r - 1]) * (s[l - 1] + s[n] - s[r - 1]));
		}
	printf("%d", min(f[1][n][0], f[1][n][1]));
    return 0;
}