洛谷 P7074 [CSP-J 2020] 方格取数

张开发
• 2026/4/10 11:41:22 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

洛谷 P7074 [CSP-J 2020] 方格取数
题目描述设有 n×m 的方格图每个方格中都有一个整数。现有一只小熊想从图的左上角走到右下角每一步只能向上、向下或向右走一格并且不能重复经过已经走过的方格也不能走出边界。小熊会取走所有经过的方格中的整数求它能取到的整数之和的最大值。输入格式第一行有两个整数 n,m。接下来 n 行每行 m 个整数依次代表每个方格中的整数。输出格式一个整数表示小熊能取到的整数之和的最大值。输入输出样例输入 #1复制3 4 1 -1 3 2 2 -1 4 -1 -2 2 -3 -1输出 #1复制9输入 #2复制2 5 -1 -1 -3 -2 -7 -2 -1 -4 -1 -2输出 #2复制-10说明/提示样例 1 解释样例 2 解释数据规模与约定对于 20% 的数据n,m≤5。对于 40% 的数据n,m≤50。对于 70% 的数据n,m≤300。对于 100% 的数据1≤n,m≤103。方格中整数的绝对值不超过 104。#includebits/stdc.h using namespace std; const int N1e310; typedef long long LL; LL f[N][N]; LL g[N][N]; LL a[N][N]; LL n,m; int main() { cinnm; for(int i1;in;i) { for(int j1;jm;j) { cina[i][j]; } } memset(f,-0x3f,sizeof f); memset(g,-0x3f,sizeof g); f[0][1]0; for(int j1;jm;j) { for(int i1;in;i) { f[i][j]max(f[i-1][j],max(f[i][j-1],g[i][j-1]))a[i][j]; } for(int in;i1;i--) { g[i][j]max(g[i1][j],max(f[i][j-1],g[i][j-1]))a[i][j]; } } coutf[n][m]endl; return 0; }

更多文章