洛谷1220题解：动态规划与区间DP优化解法（附代码注释）
8个月前 (06-26)
一、题目解读
洛谷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与动态规划的结合，将复杂的多决策问题转化为可递推的状态转移方程。前缀和的应用显著降低了计算复杂度，而分情况讨论移动方向（左/右）的耗电优化，是解题的核心技巧。此解法不仅适用于本题，也为类似区间优化问题提供了通用思路。
原创内容 转载请注明出处
