线性dp 杭电oj 1176

Question

线性dp 杭电oj 1176

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int n;
    while (scanf("%d",&n)==1&&n!=0){
        vector<int>Pos(n), Time(n);
        int Max = 0;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d%d", &Pos[i], &Time[i]);
            if (Time[i] > Max)Max = Time[i];
        }
        vector<vector<int>>dp( Max+1, vector<int>(11, -1));
        dp[0][5] = 0;
        for(int i = 0; i < n; ++i){
            if(dp[Time[i]][Pos[i]] == -1){
               dp[Time[i]][Pos[i]] = 0;
            }
            dp[Time[i]][Pos[i]]++;
        }
        for(int t = 1; t <= Max; ++t) {
            for(int p = 0; p < 11; ++p) {
                int now = dp[t][p];
                for(int k = -1; k <= 1; ++k){
                    if(p + k >= 0 && p + k < 11&&dp[t-1][p+k]!=-1) {
                        if(now == -1) now = 0;
                        dp[t][p] = max(dp[t][p], dp[t-1][p+k] + now);
                    }
                }
            }
        }
        for(int i = 0; i < 11; ++i) {
            if(dp[Max][i] != -1){
               ans = max(ans, dp[Max][i]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

一直Wrong Answer

Answer 1

晚上好🌙🌙🌙
本答案参考通义千问

你提供的代码是用于解决 杭电 OJ 1176（题目名称：免费的馅饼）的问题，这是一道典型的线性动态规划（Linear DP）问题。然而，你的代码存在一些逻辑错误，导致一直 Wrong Answer。

---

🔍 问题分析

✅ 题目大意

在一条直线上，每个时间点 t 会从某个位置 p 掉下一块馅饼。你只能站在一个位置上，每秒可以移动一个单位距离（左、右或不动）。求你能接到的最大馅饼数量。

🧠 动态规划思路

• dp[t][p] 表示在时间 t 的位置 p 上能接到的最大馅饼数。
• 每个时间点 t 的馅饼数量记录在 dp[t][p] 中。
• 状态转移方程为： $$ dp[t][p] = \max(dp[t-1][p-1], dp[t-1][p], dp[t-1][p+1]) + \text{当前馅饼数量} $$

---

❌ 代码中的问题

1. 初始状态设置不正确

   • dp[0][5] = 0; 是错误的，因为初始时刻（t=0）可能没有馅饼，所以应该初始化为 0，而不是 0。

2. 馅饼数量的统计方式错误

   • 你使用了 dp[Time[i]][Pos[i]]++，但这是错误的，因为 dp[Time[i]][Pos[i]] 初始为 -1，加上 1 后变成 0，但这不是正确的馅饼数量。

3. 状态转移逻辑错误

   • 在状态转移时，你对 now 的处理很混乱，比如 if(now == -1) now = 0; 这部分逻辑是错误的。

4. 最后取最大值的方式有误

   • 你在最后遍历所有位置，但 dp[Max][i] 可能为 -1，此时 ans = max(ans, dp[Max][i]) 会出错。

---

✅ 正确的解决方案

📌 优化后的代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n != 0) {
        vector<int> Pos(n), Time(n);
        int MaxTime = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d%d", &Pos[i], &Time[i]);
            if (Time[i] > MaxTime)
                MaxTime = Time[i];
        }

        // 初始化 dp 数组
        vector<vector<int>> dp(MaxTime + 1, vector<int>(11, -1));
        // 每个时间点的馅饼数量
        vector<vector<int>> pie(MaxTime + 1, vector<int>(11, 0));

        for (int i = 0; i < n; ++i) {
            pie[Time[i]][Pos[i]] += 1;
        }

        // 初始状态：时间0，位置5
        dp[0][5] = pie[0][5];

        for (int t = 1; t <= MaxTime; ++t) {
            for (int p = 0; p < 11; ++p) {
                if (pie[t][p] == 0) continue; // 如果该位置没有馅饼，跳过
                dp[t][p] = pie[t][p]; // 初始值为当前位置的馅饼数量
                for (int k = -1; k <= 1; ++k) {
                    int prev_p = p + k;
                    if (prev_p >= 0 && prev_p < 11 && dp[t - 1][prev_p] != -1) {
                        dp[t][p] = max(dp[t][p], dp[t - 1][prev_p] + pie[t][p]);
                    }
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < 11; ++i) {
            if (dp[MaxTime][i] != -1) {
                ans = max(ans, dp[MaxTime][i]);
            }
        }

        printf("%d\n", ans);
    }
    return 0;
}

---

✅ 关键点说明

1. pie[t][p] 用于记录每个时间点 t 在位置 p 的馅饼数量。
2. dp[t][p] 表示在时间 t 位置 p 上能接到的最大馅饼数。
3. 初始状态 设置为 dp[0][5] = pie[0][5]，表示初始时刻在位置 5 时能接到的馅饼数。
4. 状态转移 采用三方向（左、中、右），并确保只从合法位置转移过来。
5. 最终答案 是在最后时间点 MaxTime 上所有位置的最大值。

---

✅ 总结

| 问题 | 修正 | |------|------| | 初始状态错误 | 设置为 dp[0][5] = pie[0][5] | | 馅饼数量统计错误 | 使用 pie[t][p] 记录馅饼数量 | | 状态转移逻辑错误 | 使用 dp[t-1][prev_p] 来更新当前状态 | | 最终结果获取错误 | 遍历所有位置，取最大值 |

---

✅ 建议

• 尽量将 dp 和 pie 分开处理，避免混淆。
• 对于边界条件（如时间 t=0 或位置 p=0/10）要特别注意。
• 用 vector<vector<int>> 来管理二维数组，更直观清晰。

如果你还有其他疑问，欢迎继续提问！