一、问题重述
题目描述：在一条笔直的道路上安装了N盏路灯，每盏灯有位置和功率。老张从某起点出发，每秒移动1单位距离，经过的灯可以关闭（节省电量）。要求计算关闭所有灯的最小耗电量。
二、算法解析
- 问题建模 这是一个典型的区间DP问题，需要考虑：
位置信息处理 耗电量动态计算 状态转移方向性 2. 核心思想 前缀和优化：通过维护功率前缀和数组，可以O(1)计算任意区间的剩余功率总和。
状态设计三维度：
区间左右端点[i,j] 最后位置（0=左端，1=右端） 累计耗电量 3. 复杂度分析 时间复杂度：O(n²) 空间复杂度：O(n²)
- 实际应用场景 该算法思想可应用于：
资源调度问题 服务窗口选址 物流路径优化
三、C++代码实现（带详细注释）
#include <iostream>
#include <cstring>
#include <algorithm>
using namespACe std;
const int MAXN = 55;
int n, c;
int pos[MAXN], power[MAXN];
int sum[MAXN]; // 前缀和数组
int dp[MAXN][MAXN][2]; // dp[i][j][0/1]表示关闭i-j区间的灯，最后位于左/右端的最小耗电量
int main() {
cin >> n >> c;
for(int i = 1; i <= n; ++i) {
cin >> pos[i] >> power[i];
sum[i] = sum[i-1] + power[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; // 右端点
// 情况1：从i+1走到i（向左扩展）
int cost_left = (sum[n] - sum[j] + sum[i]) * (pos[i+1] - pos[i]);
dp[i][j][0] = min(dp[i+1][j][0] + cost_left,
dp[i+1][j][1] + (sum[n] - sum[j] + sum[i]) * (pos[j] - pos[i]));
// 情况2：从j-1走到j（向右扩展）
int cost_right = (sum[n] - sum[j-1] + sum[i-1]) * (pos[j] - pos[j-1]);
dp[i][j][1] = min(dp[i][j-1][1] + cost_right,
dp[i][j-1][0] + (sum[n] - sum[j-1] + sum[i-1]) * (pos[j] - pos[i]));
}
}
cout << min(dp[1][n][0], dp[1][n][1]) << endl;
return 0;
}
