一、题目解读洛谷1220题要求计算在n个位置放置灯的情况下，通过关闭连续区间灯并移动至区间端点，使得总耗电量最小。需考虑灯的功率与位置差异，设计高效的算法求解**策略。 二、解题思路1. 动态规划 + 区间DP：定义状态dp[j][0/1]表示关闭i-j区间灯后，**位于左端(i)或右端(j)的最小耗电量。 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[j][0] = min(从i+1扩展左移成本, 从i+1扩展右移后左移成本)。 ○ 计算右扩展成本：dp[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与动态规划的结合，将复杂的多决策问题转化为可递推的状态转移方程。前缀和的应用显著降低了计算复杂度，而分情况讨论移动方向（左/右）的耗电优化，是解题的核心技巧。此解法不仅适用于本题，也为类似区间优化问题提供了通用思路。
| 
发表于 2025-7-4 14:07:22
