收藏文章楼主

洛谷1220题解：动态规划与区间DP优化解法（附代码注释）

版块：SEO软文类型：普通作者：某个人查看：7 回复：0 获赞：0 时间：2025-06-28 13:20:32

洛谷1220题解：动态规划与区间DP优化解法（附代码注释）洛谷动态规划区间DP 前缀和 C++ 第1张

一、题目解读

洛谷1220题要求计算在n个位置放置灯的情况下，通过关闭连续区间灯并移动至区间端点，使得总耗电量最小。需考虑灯的功率与位置差异，设计高效的算法求解最优策略。

二、解题思路

1. 动态规划 + 区间DP：定义状态dp[i][j][0/1]表示关闭i-j区间灯后，最后位于左端(i)或右端(j)的最小耗电量。

2. 前缀和优化：使用sum数组存储灯功率前缀和，简化区间电量计算。

3. 状态转移核心：

○ 向左扩展：从i+1到i，计算移动至左端的耗电量（考虑剩余区间电量与移动距离）。

○ 向右扩展：从j-1到j，同理计算右端移动耗电。

4. 边界初始化：初始状态为单灯区间dp[c][c][0/1]=0，逐步扩展至全局最优解。

三、解题步骤

1. 输入与预处理：读取n、c及灯位置/功率，计算前缀和sum[]。

2. 初始化dp数组：全部设为无穷大，避免非法状态干扰。

3. 枚举区间长度：从2到n遍历，确保覆盖所有连续区间。

4. 状态转移循环：

○ 计算左扩展成本：dp[i][j][0] = min(从i+1扩展左移成本, 从i+1扩展右移后左移成本)。

○ 计算右扩展成本：dp[i][j][1] = min(从j-1扩展右移成本, 从j-1扩展左移后右移成本)。

5. 输出结果：比较最终区间[1,n]的左右端点耗电最小值。

四、代码与注释

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