Loading... # [洛谷 P7074 方格取数](https://www.luogu.com.cn/problem/P7074) 1e3的数据范围，仿佛是在暗示我们$O(n^2)$~~（然而并没有什么用）~~ **记忆化搜索** 时间复杂度$O(nm)$ $F_{i,j,0}$表示从一个格子上方走到该格子的路径最大和，$F_{i,j,1}$表示从一个格子下方走到该格子的路径最大和。 ## 代码 ```cpp #include <stdio.h> int n, m; long long a[1001][1001], f[1001][1001][2]; inline long long mx(const long long v1, const long long v2, const long long v3){ return v1>v2?(v1>v3?v1:v3):(v2>v3?v2:v3); } long long dfs(int x, int y, int from){ if(x<0 || x>=n || y<0 || y>=m) return -1e18; if(f[x][y][from] != -1e18) return f[x][y][from]; if(!from) f[x][y][from] = a[x][y]+mx(dfs(x+1, y, 0), dfs(x, y-1, 0), dfs(x, y-1, 1)); else f[x][y][from] = a[x][y]+mx(dfs(x-1, y, 1), dfs(x, y-1, 0), dfs(x, y-1, 1)); return f[x][y][from]; } int main(){ scanf("%d%d", &n, &m); for(int i = 0; i < n; ++i){ for(int j = 0; j < m; ++j){ scanf("%lld", &a[i][j]); f[i][j][0] = f[i][j][1] = -1e18; } } f[0][0][0] = f[0][0][1] = a[0][0]; printf("%lld\n", dfs(n-1, m-1, 1)); return 0; } ``` 参考文章 https://www.luogu.com.cn/blog/dry-ice/solution-p7074 © 允许规范转载 赞赏 如果我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付 微信支付
