二维dp测试样例都过不了,求助!

P1434 [SHOI2002] 滑雪

aojiaoluolisaiban @ 2024-03-13 20:53:23

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int ii, jj;
    cin >> ii >> jj;

    int a[105][105];
    int dp[105][105]; // 用于记录每个点的最长滑坡长度

    for (int i = 0; i < ii; i++) {
        for (int j = 0; j < jj; j++) {
            cin >> a[i][j];
            dp[i][j] = 1; // 初始化为1,因为每个点本身就构成长度为1的滑坡
        }
    }

    int fx[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 方向数组

    int maxLen = 1; // 记录最大滑坡长度

    for (int i = 0; i < ii; i++) {
        for (int j = 0; j < jj; j++) {
            for (int k = 0; k < 4; k++) {
                int x = i + fx[k][0];
                int y = j + fx[k][1];
                if (x >= 0 && x < ii && y >= 0 && y < jj && a[x][y] < a[i][j]) {
                    dp[i][j] = max(dp[i][j], dp[x][y] + 1); // 更新当前点的最长滑坡长度
                }
            }
            maxLen = max(maxLen, dp[i][j]); // 更新最大滑坡长度
        }
    }

    cout << maxLen << endl;

    return 0;
}

究竟是为什么捏??


by Composite_Function @ 2024-03-13 20:58:47

因为 @aojiaoluolisaiban 这是因为你的搜索顺序是错误的。你会发现当你在计算时 dp[i][j] 不会使用 dp[i + 1][j]dp[i][j + 1] 来计算答案。

建议:将原题改成记忆化搜索。


by aojiaoluolisaiban @ 2024-03-14 20:05:10

@Composite_Function 感谢!


|