专栏文章

P1220 关路灯 题解

zzengyukai2012
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minkhmo1
此快照首次捕获于
2025/12/02 03:53
3 个月前
此快照最后确认于
2025/12/02 03:53
3 个月前
查看原文

题目大意

一条直线上有 nn 盏路灯，第 ii 盏灯的位置为 wziwz_i（单位：米），功率为 gligl_i（单位：瓦）。老张初始位于第 cc 盏灯处，他需要关闭所有灯。他的行走速度为 1 m/s1\,\text{m/s}，关灯时间忽略不计。
每盏灯在被关闭前持续耗电，目标是安排关灯顺序，使得从开始关灯时刻起，所有灯消耗的总电能（单位：焦耳）最小。

解题思路

1. 问题转化

  • 总耗电量 = 每盏灯的功率 ×\times 它被关闭前所经过的时间。
  • 时间 = 老张走过的路径长度（速度为 11）。

2. 区间 DP 的适用性

观察发现：
  • 老张关灯的过程一定是从初始位置 cc 开始，逐步向左或向右扩展已关灯的连续区间。
  • 一旦区间 [i,j][i, j] 内的灯全部关闭，老张必定位于 ii 或 jj。
  • 后续只能关 i−1i-1 或 j+1j+1。
这符合区间动态规划的典型特征。

3. 状态定义

定义：
  • fi,j,0f_{i,j,0}：关闭区间 [i,j][i, j] 内所有灯，且当前位于 左端点 ii 时，已产生的最小总耗电量；
  • fi,j,1f_{i,j,1}：关闭区间 [i,j][i, j] 内所有灯，且当前位于 右端点 jj 时的最小总耗电量。

4. 前缀和优化

设 gl_qzhk=∑t=1kgltgl\_qzh_k = \sum_{t=1}^{k} gl_t，即功率前缀和。
则任意区间外的总功率可快速计算：
  • 区间 [i,j][i, j] 之外的灯总功率为： outside(i,j)=gl_qzhi−1+(gl_qzhn−gl_qzhj)\text{outside}(i, j) = gl\_qzh_{i-1} + (gl\_qzh_n - gl\_qzh_j)

5. 状态转移

转移到左端点 ii

从 [i+1,j][i+1, j] 扩展而来：
  • 若原在 i+1i+1：走 wzi+1−wziwz_{i+1} - wz_i；
  • 若原在 jj：走 wzj−wziwz_j - wz_i。
未关灯为 [1,i]∪(j,n][1, i] \cup (j, n]，总功率为 gl_qzhi+(gl_qzhn−gl_qzhj)gl\_qzh_{i} + (gl\_qzh_n - gl\_qzh_j)。
故：
fi,j,0=min⁡{fi+1,j,0+(gl_qzhi+gl_qzhn−gl_qzhj)⋅(wzi+1−wzi),fi+1,j,1+(gl_qzhi+gl_qzhn−gl_qzhj)⋅(wzj−wzi)f_{i,j,0} = \min\left\{ \begin{aligned} &f_{i+1,j,0} + \bigl(gl\_qzh_{i} + gl\_qzh_n - gl\_qzh_j\bigr) \cdot (wz_{i+1} - wz_i), \\ &f_{i+1,j,1} + \bigl(gl\_qzh_{i} + gl\_qzh_n - gl\_qzh_j\bigr) \cdot (wz_j - wz_i) \end{aligned} \right.

转移到右端点 jj

从 [i,j−1][i, j-1] 扩展而来：
  • 若原在 ii：走 wzj−wziwz_j - wz_i；
  • 若原在 j−1j-1：走 wzj−wzj−1wz_j - wz_{j-1}。
未关灯为 [1,i)∪[j,n][1, i) \cup [j, n]，总功率为 gl_qzhi−1+(gl_qzhn−gl_qzhj−1)gl\_qzh_{i-1} + (gl\_qzh_n - gl\_qzh_{j-1})。
故：
fi,j,1=min⁡{fi,j−1,0+(gl_qzhi−1+gl_qzhn−gl_qzhj−1)⋅(wzj−wzi),fi,j−1,1+(gl_qzhi−1+gl_qzhn−gl_qzhj−1)⋅(wzj−wzj−1)f_{i,j,1} = \min\left\{ \begin{aligned} &f_{i,j-1,0} + \bigl(gl\_qzh_{i-1} + gl\_qzh_n - gl\_qzh_{j-1}\bigr) \cdot (wz_j - wz_i), \\ &f_{i,j-1,1} + \bigl(gl\_qzh_{i-1} + gl\_qzh_n - gl\_qzh_{j-1}\bigr) \cdot (wz_j - wz_{j-1}) \end{aligned} \right.

6. 初始状态与答案

  • 初始：fc,c,0=fc,c,1=0f_{c,c,0} = f_{c,c,1} = 0；
  • 其余状态初始化为 +∞+\infty；
  • 最终答案：min⁡(f1,n,0,f1,n,1)\min(f_{1,n,0}, f_{1,n,1})。

代码实现

CPP
#include <bits/stdc++.h>
using namespace std;
int n /*路灯总数*/, c /*初始位置*/;
int wz[51] /*路灯位置*/, gl[51] /*功率*/;
int gl_qzh[51] /*功率的前缀和*/;
int f[51][51][2];
// f[i][j][0] 表示关闭从 i 到 j 的灯，现在在 i 处的总功率
// f[i][j][1] 表示关闭从 i 到 j 的灯，现在在 j 处的总功率
int main()
{
	cin >> n >> c;
	for (int i = 1; i <= n; ++i)
		cin >> wz[i] >> gl[i];
	for (int i = 1; i <= n; ++i)
		gl_qzh[i] = gl_qzh[i - 1] + gl[i];
	memset(f, 0x3f, sizeof(f)); // 初始为最大值 
	f[c][c][0] = f[c][c][1] = 0; // 初始位置
	for (int l = 1; l <= n; ++l) // 枚举区间长度 
		for (int i = 1; i <= n - l; ++i) // 枚举起点 
		{
			int j = i + l; // 终点 
			f[i][j][0] = min // 去 i 处 
			(
				f[i + 1][j][0] + // 从 i + 1 处出发 
				(gl_qzh[i] + (gl_qzh[n] - gl_qzh[j])) /*[1, i] ∪ (j, n]*/ * (wz[i + 1] - wz[i]) /*距离*/,
				f[i + 1][j][1] + // 从 j 处出发 
				(gl_qzh[i] + (gl_qzh[n] - gl_qzh[j])) /*[1, i] ∪ (j, n]*/ * (wz[j] - wz[i]) /*距离*/
			); 
			f[i][j][1] = min // 在 j 处 
			(
				f[i][j - 1][0] + // 从 i 处出发 
				(gl_qzh[i - 1] + (gl_qzh[n] - gl_qzh[j - 1])) /*[1, i) ∪ [j, n]*/ * (wz[j] - wz[i]) /*距离*/,
				f[i][j - 1][1] + // 从 j - 1 处出发 
				(gl_qzh[i - 1] + (gl_qzh[n] - gl_qzh[j - 1])) /*[1, i) ∪ [j, n]*/ * (wz[j] - wz[j - 1]) /*距离*/
			);
		}
	cout << min(f[1][n][0], f[1][n][1]) << '\n';
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...