CSP2020-J2 题解 ?? D题:方格取数

发布于:2021-09-20 03:38:01

题目相关
题目链接

目前还没有官方的题目,本题目来自洛谷,https://www.luogu.com.cn/problem/P7074?contestId=37027。


题目描述

设有 n×m 的方格图,每个方格中都有一个整数。现有一只小熊,想从图的左上角走到右下角,每一步只能向上、向下或向右走一格,并且不能重复经过已经走过的方格,也不能走出边界。小熊会取走所有经过的方格中的整数,求它能取到的整数之和的最大值。


输入

第一行有两个整数 n,m。


接下来 n 行每行 m 个整数,依次代表每个方格中的整数。


输出

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


样例 1
样例输入 1

3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1

样例输出 1

9
解释


样例 2
样例输入 2

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

样例输出 2

-10
解释


数据规模
对于 20% 的数据,n,m≤5。对于 40% 的数据,n,m≤50。对于 70% 的数据,n,m≤300。对于 100% 的数据,。方格中整数的绝对值不超过 。
题解报告
题目分析

可以使用 DP,伪码如下:


读取n,m
i 从 1 ~ n {
j 从 1 ~ m {
读取 a[i][j]
}
}

i 从 1 ~ n {
j 从 1 ~ n {
k 从 1 ~ m {
求取 DP 数组
}
}
}

1 从 n ~ 1 {
获取最大值
}

输出最大值

时间复杂度为 O(N*N*M),这个架势 70% 的数据是没问题的,还有 30% 的数据要 TLE,需要优化 DP。实话实说,目前没有想出如何优化。


其实本题和 DP 的经典题目,小卒过河,非常的相识。不同的是,小卒过河只能从上向下走。而本题可以从上向下走,也可以从下向上走。因此我们需要分开 DP 两次即可解决问题。


状态方程
定义

typedef long long LL;
const LL INF=1e18;//只要超过1e3*1e3*1e4就可以了
const int MAXN=1e3+4;
LL dp[MAXN][MAXN];//状态
int a[MAXN][MAXN];//数据

初值

//从左上角起点
dp[1][1]=a[1][1];

转移方程 1

//从上向下走
LL last=-INF;
for (int i=1; i<=n; i++) {
last=max(dp[i][j-1], last+a[i][j-1]);
dp[i][j] = last+a[i][j];
}

转移方程 2

//从下向上走
last=-INF;
for (int i=n; i>=1; i--) {
last=max(dp[i][j-1], last+a[i][j-1]);
dp[i][j]=max(dp[i][j], last+a[i][j]);
}

AC 参考代码

//https://www.luogu.com.cn/problem/P7074?contestId=37027
//P7074 方格取数
#include
using namespace std;

typedef long long LL;
const LL INF=1e18;//只要超过1e3*1e3*1e4就可以了
const int MAXN=1e3+4;
LL dp[MAXN][MAXN];//状态
int a[MAXN][MAXN];//数据

int main() {
#if 1
//提交OJ使用快读
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#endif

//读取数据
int n,m;
cin>>n>>m;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
cin>>a[i][j];
}
}

//初始化
dp[1][1]=a[1][1];
for (int i=2; i<=n; i++) {
dp[i][1]=-INF;
}

//状态转移
LL last;
for (int j=2; j<=m; j++) {
//从上向下走
last=-INF;
for (int i=1; i<=n; i++) {
last=max(dp[i][j-1], last+a[i][j-1]);
dp[i][j] = last+a[i][j];
}

//从下向上走
last=-INF;
for (int i=n; i>=1; i--) {
last=max(dp[i][j-1], last+a[i][j-1]);
dp[i][j]=max(dp[i][j], last+a[i][j]);
}
}

//查找答案
LL ans=-INF;
last=0;
for (int i=n; i>=1; i--) {
ans = max(ans, dp[i][m]+last);
last += a[i][m];
}

cout<";

return 0;
}

下图是没有使用快读的时间记录。



下图是使用了快读的时间记录。



快读结论

在提交代码的时候,还是需要使用快读的,速度能快很多。本地调试的时候,不要使用快读。


时间复杂度

O(N*M)。

相关推荐