[CSP2020]方格取数（number）

NC213852. [CSP2020]方格取数（number）

描述

题目数据为官方数据，可以提交测试，结果仅供参考，不代表官方成绩，最终成绩以官方发布的最终成绩为准。

设有 $𝑛 × 𝑚$ 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，

求它能取到的整数之和的最大值。

输入描述

第 1 行两个正整数 。
接下来  行每行  个整数，依次代表每个方格中的整数。

输出描述

一个整数，表示小熊能取到的整数之和的最大值。

示例1

输入:

输出:

说明:

按上述走法，取到的数之和为 1 + 2 + (-1) + 4 + 3 + 2 + (-1) + (-1) = 9，可以证明为最大值。

注意，上述走法是错误的，因为第 $2$ 行第 $2$ 列的方格走过了两次，而根据题意，不能重复经过已经走过的方格。

另外，上述走法也是错误的，因为没有走到右下角的终点。

示例2

输入:

2 5
-1 -1 -3 -2 -7
-2 -1 -4 -1 -2

输出:

-10

说明:

按上述走法，取到的数之和为(-1) + (-1) + (-3) + (-2) + (-1) + (-2) = -10，可以证明为最大值。因此，请注意，取到的数之和的最大值也可能是负数。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 236ms, 内存消耗: 12356K, 提交时间: 2022-10-03 12:10:53

#include<bits/stdc++.h>
using namespace std;
int a[1010][1010];
long long f[1010][1010];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	memset(f,-0x7f,sizeof(f));
	long long ma;
	f[1][0]=0;
	for(int j=1;j<=m;j++)
	{
		ma=-1e18;
		for(int i=1;i<=n;i++)
		{
			ma=max(ma,f[i][j-1])+a[i][j];
			f[i][j]=max(f[i][j],ma);
		}
		ma=-1e18;
		for(int i=n;i>=1;i--)
		{
			ma=max(ma,f[i][j-1])+a[i][j];
			f[i][j]=max(f[i][j],ma);
		}
	}
	cout<<f[n][m]<<endl;
	
	return 0;
}

上一题

下一题

详情