洛谷 P1220 分析（别看）

科技起源

2026-07-08 12:14:26

发布于：河北

5阅读

0回复

0点赞

原题链接

注：本篇文章中所有的“区间 $[i,j]$ ”是指所有编号在 $i$ 到 $j$ 之间的灯

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：有 $n$ 个灯，每个灯有功率与其位置（表示为到起点的距离，单位：米），还有一个起点 $c$
允许：从起点出发，先关掉起点的灯，接着每次可以往左/右若干米，沿途中经过的所有灯都会被关闭，关闭后将不再耗电，求将所有灯都关闭后耗电量最小是多少
禁止：
限制：既然“沿途中经过的所有灯都会被关闭”，那我们可以得到很重要的一个结论：关掉区间 $[i,j]$ 的所有灯后，只会位于 $i$ 或者 $j$ 上

1.3 题目数据范围与猜测

$1 \le n \le 50 \longrightarrow O(n^4)$

1.4 一句话概括题意

有一些灯，每个灯有功率与其位置（表示为到起点的距离，单位：米），还有一个起点。从起点出发，先关掉起点的灯，接着每次可以往左/右若干米，沿途中经过的所有灯都会被关闭，关闭后将不再耗电，求将所有灯都关闭后耗电量最小是多少

2 题目破题推导

注：以下七种方法都可以考虑一下

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

正向思维：尝试选择最优方案
逆向思维：关键性质推导（最优方案是怎么来的，长什么样子）：最优路径一定不会跳过某一盏灯，否则还需要折返回来，一定不是最优方案。那么对于每时每刻：已经关掉的灯一定是一段连续的区间
那就不能用正向思维的方法以起点为 $c$ 不断扩散了
而是应该以终点为 $[c,c]$ 开始每次往左/右端点扩展一格，直到 $[1,n]$

2.3 分情况考虑

大区间 $[l,r]$ 只有几种可能：

上一步关掉了 $[l+1,r]$ ，上一步在 $l+1$ 时在这次走到了 $l$
上一步关掉了 $[l+1,r]$ ，上一步在 $r$ 时在这次走到了 $l$
上一步关掉了 $[l,r-1]$ ，上一步在 $l$ 时在这次走到了 $r$
上一步关掉了 $[l,r-1]$ ，上一步在 $r-1$ 时在这次走到了 $r$

2.4 数学

如果已经关闭了区间 $[i,j]$ 的所有灯，那么 $t$ 分钟的总耗电量即为 $t \times (区间[1,i-1]的灯的每分钟耗电量+区间[j+1,n]的灯的每分钟耗电量$

2.5 以终为始、以始为终

2.6 手动推导

2.7 边界测试

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：区间，时刻求取最小值 $\longrightarrow$ $\huge{区间动态规划}$
关键词：区间求和 $\longrightarrow$ $\huge{前缀和优化}$

3.1 需要注意的点

dp数组的定义：
先定义模板，发现对于刚刚的“分情况考虑”，会失去推导“这次走到了哪里”以及“下次从这里可以走到哪里”的能力，因此考虑扩维
定义 ${{dp_i}_j}_0$ 代表已关完连续区间 $[l,r]$ ，人站在左端点 $l$ ，最小总耗电
定义 ${{dp_i}_j}_1$ 代表已关完连续区间 $[l,r]$ ，人站在右端点 $r$ ，最小总耗电

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

const int N = 111;
int a[N], b[N];
int sum[N];
int n, m, c;
int dp[N][N][2];

int main(){
	
	cin >> n >> c;
	for (int i = 1;i <= n;i++){
		cin >> a[i] >> b[i];
	}
	for (int i = 1;i <= n;i++){
		sum[i] = sum[i - 1] + b[i];
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[c][c][0] = dp[c][c][1] = 0;
	for (int len = 2;len <= n;len++){
		for (int i = 1;i + len - 1 <= n;i++){
			int j = i + len - 1;
			dp[i][j][0] = min(dp[i + 1][j][0] + (a[i + 1] - a[i]) * (sum[i] + sum[n] - sum[j]), dp[i + 1][j][1] + (a[j] - a[i]) * (sum[i] + sum[n] - sum[j]));
			dp[i][j][1] = min(dp[i][j - 1][0] + (a[j] - a[i]) * (sum[i - 1] + sum[n] - sum[j - 1]), dp[i][j - 1][1] + (a[j] - a[j - 1]) * (sum[i - 1] + sum[n] - sum[j - 1]));
		}
	}
	cout << min(dp[1][n][0], dp[1][n][1]);
	
	return 0;
}