动态规划的，我chat一次有一次

Question

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <unordered_set>

using namespace std;

int dfs(int L, int M, int S, int T, const vector<int>& cake_positions) {
    vector<int> dp(L + 1, INT_MAX);
    if (cake_positions[0] == 0) // 如果第一个位置是陷阱
        dp[1] = 1;
    else
        dp[1] = 0;

    unordered_set<int> cakes(cake_positions.begin(), cake_positions.end());

    for (int i = 1; i <= L; ++i) {
        if (cakes.count(i) == 0 || dp[i] == INT_MAX) {
            continue;
        }
        
        for (int j = S; j <= T; ++j) {
            int next_position = i + j;
            if (next_position <= L) {
                dp[next_position] = min(dp[next_position], dp[i] + 1);
            }
        }
    }

    return dp[L] == INT_MAX ? -1 : dp[L];
}

int main() {
    int L, M, S, T;
    cin >> L >> M;
    cin >> S >> T;

    vector<int> cake_positions(M);
    for (int i = 0; i < M; ++i) {
        cin >> cake_positions[i];
    }

    int result = dfs(L, M, S, T, cake_positions);
    cout << result << endl;

    return 0;
}

实在不懂chat出的答案怎么也改不对，输出一直是-1，寄了

Answer 1

引自免费微信小程序：皆我百晓生

从你提供的代码来看，主要的问题在于动态规划的状态转移方式与初始化条件上存在错误。在动态规划中，状态dp[i]应该表示达到位置i时最少踩到的陷阱数量，而不是仅当当前位置i是陷阱时才进行状态更新。

问题分析与修正思路

1. 初始化：dp数组的初始化应该考虑所有位置，而不仅仅是陷阱位置。对于每个位置，dp[i]应该初始化为INT_MAX，除了dp[0]应该初始化为0，因为开始位置没有陷阱。

2. 状态转移：在状态转移过程中，应该从所有可能的前一步位置i开始，尝试跳跃到下一个位置next_position。如果next_position是一个陷阱，则在更新dp[next_position]时增加陷阱数量。

3. 陷阱列表处理：陷阱列表应该先排序，这样可以优化查找过程，但在本题中并非必要，因为状态转移过程中会遍历所有位置。

4. 输出处理：如果dp[L]仍然等于INT_MAX，意味着无法到达终点，应输出-1。否则输出dp[L]。

修改后的代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int dfs(int L, int M, int S, int T, const vector<int>& cake_positions) {
    vector<int> dp(L + 1, INT_MAX);
    dp[0] = 0; // 初始位置没有陷阱

    sort(cake_positions.begin(), cake_positions.end()); // 可选排序，这里不影响结果

    for (int i = 0; i <= L; ++i) {
        if (dp[i] != INT_MAX) { // 只有可到达的位置才进行状态转移
            for (int j = S; j <= T; ++j) {
                int next_position = i + j;
                if (next_position <= L) {
                    int trap_here = find(cake_positions.begin(), cake_positions.end(), next_position) != cake_positions.end();
                    dp[next_position] = min(dp[next_position], dp[i] + trap_here);
                }
            }
        }
    }

    return dp[L] == INT_MAX ? -1 : dp[L];
}

int main() {
    int L, M, S, T;
    cin >> L >> M;
    cin >> S >> T;

    vector<int> cake_positions(M);
    for (int i = 0; i < M; ++i) {
        cin >> cake_positions[i];
    }

    int result = dfs(L, M, S, T, cake_positions);
    cout << result << endl;

    return 0;
}

注意点

• 在状态转移过程中，我们检查dp[i]是否不是INT_MAX，这确保只有从可达位置出发才能进行下一步的计算。
• 使用find函数来检查next_position是否为陷阱。如果next_position不在cake_positions中，则trap_here为0，否则为1。
• dp[0]的初始化为0，表示起点没有陷阱。

这个修改后的代码应该能正确地解决你提到的问题，并输出正确的结果。