CSP-J 2020方格取数题解-北京尧图网络

题目描述给定 n*m的方格每个格子有整数。小熊从左上角(0,0)走到右下角(n‑1,m‑1)。每一步只能向上、向下、向右不能重复经过格子不能越界。求取到格子数字总和的最大值。注意不能向左走一旦走到下一列就再也回不到左边列否则格子会重复访问。也就是说路径一定是按列推进。同一列内部可以上下来回走但是不能回到左侧已经处理完的列。思路一暴力 DFS(25分)直接暴力搜索标记 vis 访问向上 / 下 / 右递归搜索到达终点更新答案。#includebits/stdc.husingnamespacestd;intn,m,maxnINT_MIN;inta[1005][1005];intdx[3]{-1,1,0};intdy[3]{0,0,1};boolvis[1005][1005];voiddfs(intx,inty,intsum){if(xn-1ym-1){maxnmax(maxn,sum);return;}for(inti0;i3;i){intnxxdx[i],nyydy[i];if(nx0nxnny0nym!vis[nx][ny]){vis[nx][ny]true;dfs(nx,ny,suma[nx][ny]);vis[nx][ny]false;}}}intmain(){cinnm;for(inti0;in;i){for(intj0;jm;j){cina[i][j];}}vis[0][0]true;dfs(0,0,a[0][0]);coutmaxn;return0;}问题n,m1000网格总共有 10^6个格子DFS 搜索状态爆炸只能过小数据。思路二记忆化 DFS不能向左走只能向上、向下、向右。到达(x,y)的时候我们只需要记录是从哪个方向来到当前格子。from 0从左边(y‑1)向右走过来from 1从上边(x‑1)向下走过来from 2从下边(x1)向上走过来如果是从上方来from1就不能再向上走防止回头重复如果是从下方来from2就不能再向下走防止回头重复。状态定义dp[x][y][from]在(x,y)由from方向抵达走到终点的最大权值和。转移向右走到(y1)来源标记为0如果不是从上方过来可以向上走来源标记2如果不是从下方过来可以向下走来源标记1。#includebits/stdc.husingnamespacestd;intn,m;inta[1005][1005];intdx[3]{-1,1,0};intdy[3]{0,0,1};boolvis[1005][1005][3];longlongdp[1005][1005][3];//记忆化 0左边过来1上面2下面longlongdfs(intx,inty,intfrom){if(xn-1ym-1){returna[x][y];}if(vis[x][y][from])returndp[x][y][from];vis[x][y][from]true;longlongbest-1e18;if(y1m)//向右走{bestmax(best,dfs(x,y1,0));}if(from!1x-10)//向上走{bestmax(best,dfs(x-1,y,2));}if(from!2x1n)//向下走{bestmax(best,dfs(x1,y,1));}dp[x][y][from]a[x][y]best;returndp[x][y][from];}intmain(){cinnm;for(inti0;in;i){for(intj0;jm;j){cina[i][j];}}memset(vis,0,sizeof(vis));coutdfs(0,0,0);return0;}这种方法虽然在洛谷里能过但是卡着极限过的。思路三递推 DP(正解)核心性质路径不允许向左走因此处理完第j‑1整列再处理第 j 列。同一列 j 内部可以先从上往下扫一遍再从下往上扫一遍。状态定义:dp[i][j]走到第 i 行第 j 列格子并且结束在(i,j)的最大总和。#includebits/stdc.husingnamespacestd;intn,m;inta[1005][1005];longlongdp[1005][1005];intmain(){cinnm;for(inti0;in;i){for(intj0;jm;j){cina[i][j];}}for(inti0;in;i){for(intj0;jm;j){dp[i][j]-1e18;}}dp[0][0]a[0][0];//第一列从上往下走for(inti1;in;i){dp[i][0]dp[i-1][0]a[i][0];}//处理每一列for(intj1;jm;j){//从上往下longlongd[1005];d[0]dp[0][j-1]a[0][j];for(inti1;in;i){d[i]max(dp[i][j-1],d[i-1])a[i][j];}//从下往上longlongu[1005];u[n-1]dp[n-1][j-1]a[n-1][j];for(intin-2;i0;i--){u[i]max(dp[i][j-1],u[i1])a[i][j];}//最大值for(inti0;in;i){dp[i][j]max(d[i],u[i]);}}coutdp[n-1][m-1];return0;}

CSP-J 2020方格取数题解

相关推荐

第10讲：MCP Server 生产化部署

如何用AlwaysOnTop彻底解决Windows窗口管理的三大痛点？

ArcGIS基础工具条核心功能解析：从导航到测量的GIS入门指南

更多资讯

多模态感知融合与MPC：移动机器人动态路径规划实战

BAT32G113仿真调试与量产烧录实战：从Keil配置到脱机烧录器

3ds Max环境艺术入门：系统设置与Vray渲染基础

深度强化学习在电网调度与微电网能量管理中的实战应用

数据结构与算法PPT高效复习：从知识骨架到代码实战

自抗扰控制ADRC核心原理与工程实践：从PID到ESO扰动抑制

今日更新

45个经典Linux面试题：从命令到网络排障的完整考点解析

SAP生产预留实战指南：MB21/MB23/MB25协同与MRP集成

编译原理实验：递归下降分析器消除左递归与避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？