【动态规划 前缀和】P7074 [CSP-J2020] 方格取数|普及+

本文涉及知识点

C++动态规划 C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

P7074 [CSP-J2020] 方格取数

题目描述

设有

n

×

m

n \\times m

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

输入格式

第一行有两个整数

n

,

m

n, m

n,m。

接下来

n

n

n 行每行

m

m

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

说明/提示

样例 1 解释

样例 2 解释

数据规模与约定

• 对于 $20\%$
• 对于 $40\%$
• 对于 $70\%$
• 对于 $100\%$

2024/2/4 添加一组 hack 数据。

动态规划

R,C代替n,m。 性质一：不能经过已经经过的单格。故不会有环。

动态规划的状态表示：

dp[c][r]表示第c列最后的单格是(r,c)的最大收益。空间复杂度：O(RC) 动态规划的填报顺序 枚举前置状态，c从0到C-2,r从0到R-1 动态规划的转移方程 枚举后置状态是：(r1,c+1) MaxSelf(dp[r1][c+1],dp[r][c] + mat[r1…r][c+1]之和) 时间复杂度：O(RRC) 动态规划的初始值 dp[0][r] = mat[0…r][0]之和。 动态规划的返回值 dp.back().back()

优化，枚举后序状态

如果r <= r1，则dp[r][c] + mat[0…r1][c+1] – mat[0…r-1][c+1] ,我们只需要记录max(dp[r][c]-mat[0…r-1][c+1]) 如果r > r1，则dp[r][c] + mat[0…r][c+1]- mat[0…r1-1][c+1]，我们只需要记录max(dp[r][c] + mat[0…r][c+1]) 如果r == r1 dp[r][c] + mat[r][c+1] 单个状态时间复杂度：O(1)，总时间复杂度：O(RC)

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>

#include <bitset>
using namespace std;

template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
in >> pr.first >> pr.second;
return in;
}

template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t);
return in;
}

template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
return in;
}

template<class T = int>
vector<T> Read() {
int n;
cin >> n;
vector<T> ret(n);
for (int i = 0; i < n; i++) {
cin >> ret[i];
}
return ret;
}
template<class T = int>
vector<T> ReadNotNum() {
vector<T> ret;
T tmp;
while (cin >> tmp) {
ret.emplace_back(tmp);
if ('\\n' == cin.get()) { break; }
}
return ret;
}

template<class T = int>
vector<T> Read(int n) {
vector<T> ret(n);
for (int i = 0; i < n; i++) {
cin >> ret[i];
}
return ret;
}

class CNeiBo
{
public:
static vector<vector<int>> Two(int n, const vector<pair<int, int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<int>> vNeiBo(n);
for (const auto& [i1, i2] : edges)
{
vNeiBo[i1 – iBase].emplace_back(i2 – iBase);
if (!bDirect)
{
vNeiBo[i2 – iBase].emplace_back(i1 – iBase);
}
}
return vNeiBo;
}
static vector<vector<int>> Two(int n, const vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<int>> vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo[v[0] – iBase].emplace_back(v[1] – iBase);
if (!bDirect)
{
vNeiBo[v[1] – iBase].emplace_back(v[0] – iBase);
}
}
return vNeiBo;
}
static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<std::pair<int, int>>> vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo[v[0] – iBase].emplace_back(v[1] – iBase, v[2]);
if (!bDirect)
{
vNeiBo[v[1] – iBase].emplace_back(v[0] – iBase, v[2]);
}
}
return vNeiBo;
}
static vector<vector<std::pair<int, int>>> Three(int n, const vector<tuple<int, int, int>>& edges, bool bDirect, int iBase = 0)
{
vector<vector<std::pair<int, int>>> vNeiBo(n);
for (const auto& [u, v, w] : edges)
{
vNeiBo[u – iBase].emplace_back(v – iBase, w);
if (!bDirect)
{
vNeiBo[v – iBase].emplace_back(u – iBase, w);
}
}
return vNeiBo;
}
static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
{
vector<vector<int>> neiBo(neiBoMat.size());
for (int i = 0; i < neiBoMat.size(); i++)
{
for (int j = i + 1; j < neiBoMat.size(); j++)
{
if (neiBoMat[i][j])
{
neiBo[i].emplace_back(j);
neiBo[j].emplace_back(i);
}
}
}
return neiBo;
}
};

class Solution {
public:
long long Ans(const int R, const int C, vector<vector<int>>& mat) {
vector<long long> pre(R);
{
long long sum = 0;
for (int r = 0; r < R; r++) { sum += mat[r][0]; pre[r] = sum; }
}
for (int c = 0; c + 1 < C; c++) {
vector<long long> cur(R, LLONG_MIN / 2);
long long sum = 0, llMax = LLONG_MIN / 2;
for (int r = 0; r < R; r++) {//下移
cur[r] = max(cur[r], mat[r][c + 1] + sum + llMax);
llMax = max(llMax, pre[r] – sum);
sum += mat[r][c + 1];
}
for (int r = 0; r < R; r++) {//平移
cur[r] = max(cur[r], pre[r] + mat[r][c + 1]);
}
sum = 0, llMax = LLONG_MIN / 2;
for (int r = R – 1; r >= 0; r—) {//上移
cur[r] = max(cur[r], mat[r][c + 1] + sum + llMax);
llMax = max(llMax, pre[r] – sum);
sum += mat[r][c + 1];
}
pre.swap(cur);
}
return pre.back();
}
};

int main() {
#ifdef _DEBUG
freopen("a.in", "r", stdin);
#endif // DEBUG
ios::sync_with_stdio(0); cin.tie(nullptr);
int R,C;
cin >> R >> C;
vector<vector<int>> mat(R);
for (int r = 0; r < R; r++) {
mat[r] = Read<int>(C);
}
#ifdef _DEBUG
printf("R=%d,C=%d",R,C);
Out(mat, ",mat=");
//Out(a, ",a=");
//Out(que, ",que=");
/*Out(que, "que=");*/
#endif // DEBUG
auto res = Solution().Ans(R,C,mat);
cout << res;
return 0;
}

单元测试

int R,C;
vector<vector<int>> mat;
TEST_METHOD(TestMethod1)
{
R = 3, C = 4, mat = { {1,–1,3,2},{2,–1,4,–1},{–2,2,–3,–1} };
auto res = Solution().Ans(R,C,mat);
AssertEx(9LL, res);
}
TEST_METHOD(TestMethod2)
{
R = 2, C = 5, mat = { {–1,–1,–3,–2,–7},{–2,–1,–4,–1,–2} };
auto res = Solution().Ans(R, C, mat);
AssertEx(–10LL, res);
}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程 https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17 或者 操作系统：win10 开发环境： VS2022 C++17 如无特殊说明，本算法用**C++**实现。