动态规划实战：洛谷P1220关路灯问题最优解（附C++代码 AC100）

一、问题重述

题目描述：在一条笔直的道路上安装了N盏路灯，每盏灯有位置和功率。老张从某起点出发，每秒移动1单位距离，经过的灯可以关闭（节省电量）。要求计算关闭所有灯的最小耗电量。

二、算法解析

1. 问题建模

这是一个典型的区间DP问题，需要考虑：

• 位置信息处理

• 耗电量动态计算

• 状态转移方向性

2. 核心思想

前缀和优化：通过维护功率前缀和数组，可以O(1)计算任意区间的剩余功率总和。

状态设计三维度：

• 区间左右端点[i,j]

• 最后位置（0=左端，1=右端）

• 累计耗电量

3. 复杂度分析

时间复杂度：O(n²) 空间复杂度：O(n²)

4. 实际应用场景

该算法思想可应用于：

• 资源调度问题

• 服务窗口选址

• 物流路径优化

三、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;
}

四、优化技巧

1. 剪枝策略：当区间长度较小时可以直接计算

2. 记忆化搜索：可采用递归+记忆化的实现方式

3. 滚动数组：可优化空间复杂度到O(n)

五、常见错误排查

1. 初始化问题：确保起点状态正确

2. 边界处理：注意数组越界情况

3. 状态转移公式：验证功率计算是否正确