原题链接
> 注：本篇文章中所有的“区间 [i,j][i,j][i,j]”是指所有编号在 iii 到 jjj之间的灯
1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个最小值
1.2 题目背景、允许、禁止与限制
背景：有 nnn 个灯，每个灯有功率与其位置（表示为到起点的距离，单位：米），还有一个起点 ccc
允许：从起点出发，先关掉起点的灯，接着每次可以往左/右若干米，沿途中经过的所有灯都会被关闭，关闭后将不再耗电，求将所有灯都关闭后耗电量最小是多少
限制：既然“沿途中经过的所有灯都会被关闭”，那我们可以得到很重要的一个结论：关掉区间 [i,j][i,j][i,j] 的所有灯后，只会位于 iii 或者 jjj 上
1.3 题目数据范围与猜测
1≤n≤50⟶O(n4)1 \le n \le 50 \longrightarrow O(n^4)1≤n≤50⟶O(n4)
1.4 一句话概括题意
有一些点，每个点有两个信息 (花费,与原点的距离)(花费,与原点的距离)(花费,与原点的距离)，每经过111 单位时间，所有未熄灭的点将会使花费增加所有未熄灭点的花费，给定一个起始点。从起始点出发，先熄灭该点，接着每次可以往左/右若干单位距离，沿途中经过的所有点都会熄灭，熄灭后将不再增加花费，求将所有点都熄灭后总花费的最小值
2 题目破题推导
2.1 第一步：正向思维转逆向思维+以终为始以始为终
正向思维：尝试选择最优方案
逆向思维：关键性质推导（最优方案是怎么来的，长什么样子）：最优路径一定不会跳过某一盏灯，否则还需要折返回来，一定不是最优方案。那么对于每时每刻：已经关掉的灯一定是一段连续的区间
那就不能用正向思维的方法以起点为 ccc 不断扩散了
而是应该以终点为 [c,c][c,c][c,c] 开始每次往左/右端点扩展一格，直到 [1,n][1,n][1,n]
2.2 第二步：分情况考虑
大区间 [l,r][l,r][l,r] 只有几种可能：
* 上一步关掉了 [l+1,r][l+1,r][l+1,r]，上一步在 l+1l+1l+1 时在这次走到了 lll
* 上一步关掉了 [l+1,r][l+1,r][l+1,r]，上一步在 rrr 时在这次走到了 lll
* 上一步关掉了 [l,r−1][l,r-1][l,r−1]，上一步在 lll 时在这次走到了 rrr
* 上一步关掉了 [l,r−1][l,r-1][l,r−1]，上一步在 r−1r-1r−1 时在这次走到了 rrr
2.3 第三步：数学
如果已经关闭了区间 [i,j][i,j][i,j] 的所有灯，那么 ttt 分钟的总耗电量即为 t×(区间[1,i−1]的灯的每分钟耗电量+区间[j+1,n]的灯的每分钟耗电量t \times (区间[1,i-1]的灯的每分钟耗电量+区间[j+1,n]的灯的每分钟耗电量t×(区间[1,i−1]的灯的每分钟耗电量+区间[j+1,n]的灯的每分钟耗电量
3 模型匹配
关键词：区间，时刻求取最小值 ⟶\longrightarrow⟶ 区间动态规划\huge{区间动态规划}区间动态规划
关键词：区间求和 ⟶\longrightarrow⟶ 前缀和优化\huge{前缀和优化}前缀和优化
3.1 需要注意的点
dp数组的定义：
先定义模板，发现对于刚刚的“分情况考虑”，会失去推导“这次走到了哪里”以及“下次从这里可以走到哪里”的能力，因此考虑扩维
定义 dp[i][j][0]dp[i][j][0]dp[i][j][0] 代表已关完连续区间 [l,r][l,r][l,r]，人站在左端点 lll，最小总耗电
定义 dp[i][j][1]dp[i][j][1]dp[i][j][1] 代表已关完连续区间 [l,r][l,r][l,r]，人站在右端点 rrr，最小总耗电
4 最终代码（禁止抄袭，仅用于参考）
