当前位置:首页 > 洛谷 > 洛谷1220题解:动态规划与区间DP优化解法(附代码注释)

洛谷1220题解:动态规划与区间DP优化解法(附代码注释)

2个月前 (06-26)

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

五、总结

洛谷1220通过区间DP与动态规划的结合,将复杂的多决策问题转化为可递推状态转移方程。前缀和的应用显著降低了计算复杂度,而分情况讨论移动方向(左/右)的耗电优化,是解题的核心技巧。此解法不仅适用于本题,也为类似区间优化问题提供了通用思路。


原创内容 转载请注明出处

分享给朋友:

相关文章

力扣5:中心扩散法 轻松破解最长回文子串

力扣5:中心扩散法 轻松破解最长回文子串

题目解读:在一个给定的字符串中,我们需要找到最长的回文子串。回文是指正读反读都相同的字符串,如"aba"、"abba"都是回文。这个问题看似简单,但要在字符串中...

力扣540题:线性扫描法如何高效定位唯一数

力扣540题:线性扫描法如何高效定位唯一数

题目重解一个严格递增的有序数组中,除某个元素外,其余每个元素均出现两次。这个看似简单的条件背后隐藏着巧妙的规律——单一元素会打破数组的"成对对称性"。题目要求以O(log n)时间...

2024年GESP五级武器强化(洛谷B4071)解题代码C++版

2024年GESP五级武器强化(洛谷B4071)解题代码C++版

一、题目解读    2024年GESP(青少年软件编程能力等级考试)五级中的“武器强化”(洛谷平台题目编号B4071)是一道典型的算法优化问题。题目要求通过合理...

手搓顺序表类代码注释与详解:从零实现动态数组(新手教程)

一、简介和特点顺序表(Sequential List)是数据结构中基础的一种线性表,其特点是将数据元素存储在连续的内存空间中。通过数组实现,支持随机访问(即通过索引直接访问元素),适用于频繁随机读取的...

NOIP 2008火柴棒等式题解(C++代码实现)  动态规划与枚举算法详解

NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解

一、题目解读火柴棒等式问题(NOIP 2008,洛谷P1149)要求使用给定数量的火柴棒,构造形如 A + B = C 的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式...

【蓝桥杯2015省赛解析】生命之树:树形DP解题全攻略(洛谷P8625代码详解)

【蓝桥杯2015省赛解析】生命之树:树形DP解题全攻略(洛谷P8625代码详解)

一、题目解读    “生命之树”是一道经典的树形结构问题,要求计算一棵带权树中,以某个节点为根的最大子树权值和。题目输入为n个节点及边信息,每个节点有权值wi,...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。