动态规划实战:洛谷P1220关路灯问题最优解(附C++代码 AC100)

文章封面

截图未命名 一、问题重述 题目描述:在一条笔直的道路上安装了N盏路灯,每盏灯有位置和功率。老张从某起点出发,每秒移动1单位距离,经过的灯可以关闭(节省电量)。要求计算关闭所有灯的最小耗电量。

二、算法解析

  1. 问题建模 这是一个典型的区间DP问题,需要考虑:

位置信息处理 耗电量动态计算 状态转移方向性 2. 核心思想 前缀和优化:通过维护功率前缀和数组,可以O(1)计算任意区间的剩余功率总和。

状态设计三维度:

区间左右端点[i,j] 最后位置(0=左端,1=右端) 累计耗电量 3. 复杂度分析 时间复杂度:O(n²) 空间复杂度:O(n²)

  1. 实际应用场景 该算法思想可应用于:

资源调度问题 服务窗口选址 物流路径优化

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

原文:动态规划实战:洛谷P1220关路灯问题最优解(附C++代码 AC100)

评论

暂无评论