记忆化为什么不对???
查看原帖
记忆化为什么不对???
370532
SuAnRan楼主2023/6/2 22:31
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int r, c;
int a[110][110];
int f[110][110];
int dx[3] = {0, -1, 1};
int dy[3] = {-1, -1, -1};

int dp(int x, int y)
{
    if(f[x][y] != -1) return f[x][y];

    int &v = f[x][y];

    for(int i = 0; i < 3; i ++)
    {
        int dxx = x + dx[i];
        int dyy = y + dy[i];
        if(dxx >= 1 && dxx <= r && dyy >= 1 && dyy <= c)
        {
            v = max(v, dp(dxx, dyy) + a[x][y]);
        }
    }

    return v;
}

int main()
{
    cin >> r >> c;

    for(int i = 1; i  <= r; i ++)
        for(int j = 1; j <= c; j ++) cin >> a[i][j];
    
    int ans = 0;

    memset(f, -1, sizeof f);

    f[1][1] = a[1][1];

    for(int i = 1; i <= r; i ++)
        for(int j = 1; j <= c; j ++)
        {
            ans = max(ans, dp(i, j));
           // cout << dp(i, j) << endl;
        }

    cout << ans << endl;
}
2023/6/2 22:31
加载中...