信奥赛C++提高组csp-s之搜索进阶（记忆化搜索案例实践3）

信奥赛C提高组csp-s之搜索进阶记忆化搜索案例实践3方格取数题目描述设有n × m n \times mn×m的方格图每个方格中都有一个整数。现有一只小熊想从图的左上角走到右下角每一步只能向上、向下或向右走一格并且不能重复经过已经走过的方格也不能走出边界。小熊会取走所有经过的方格中的整数求它能取到的整数之和的最大值。输入格式第一行有两个整数n , m n, mn,m。接下来n nn行每行m mm个整数依次代表每个方格中的整数。输出格式一个整数表示小熊能取到的整数之和的最大值。输入输出样例 1输入 13 4 1 -1 3 2 2 -1 4 -1 -2 2 -3 -1输出 19输入输出样例 2输入 22 5 -1 -1 -3 -2 -7 -2 -1 -4 -1 -2输出 2-10说明/提示样例 1 解释样例 2 解释数据规模与约定对于20 % 20\%20%的数据n , m ≤ 5 n, m \le 5n,m≤5。对于40 % 40\%40%的数据n , m ≤ 50 n, m \le 50n,m≤50。对于70 % 70\%70%的数据n , m ≤ 300 n, m \le 300n,m≤300。对于100 % 100\%100%的数据1 ≤ n , m ≤ 10 3 1 \le n,m \le 10^31≤n,m≤103。方格中整数的绝对值不超过10 4 10^4104。思路分析题目大意在 n×m 的方格图中每个方格有一个整数。小熊从左上角(1,1)走到右下角(n,m)每一步可以向上、向下或向右走一格不能重复经过已经走过的方格求经过的整数和的最大值。分析思路这道题的特殊性在于可以向上、向下、向右走但不能向左走。这意味着对于某个点(x, y)小熊可能是从下面来的也可能是从上面来的路径走向直接影响后续可达状态。因此需要在状态中加入方向信息设f[x][y][k]表示到达(x, y)时能取到的最大整数和k 0从下方来到该点k 1从上方来到该点从左边来不需要单独标识因为向左走被禁止采用逆向搜索更简便从(n, m)向(1, 1)搜索递归考虑每一步的来源方向。代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintN1005;constll INF2e18;intn,m;ll a[N][N];// 存储方格中的数值ll f[N][N][2];// f[x][y][k]到达(x,y)时的最大值k0从下方来k1从上方来lldfs(intx,inty,intk){// 边界条件出界返回负无穷if(x1||xn||y1||ym)return-INF;// 起点只有(1,1)才能直接返回if(x1y1)returna[1][1];// 记忆化已经计算过直接返回if(f[x][y][k]!-INF)returnf[x][y][k];ll ans-INF;// 从左边来不管k是0还是1都可以从左边来ansmax(ans,dfs(x,y-1,0));// 左边点不管从哪来ansmax(ans,dfs(x,y-1,1));// 根据k决定是否可以从上方或下方来if(k0){// 当前点是从下方来的那么上一个点只能在它的下方不能往上因为不能折返ansmax(ans,dfs(x1,y,0));// 从下方来}else{// k 1当前点是从上方来的ansmax(ans,dfs(x-1,y,1));// 从上方来}// 加上当前点的数值存入备忘录并返回returnf[x][y][k]ansa[x][y];}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinnm;for(inti1;in;i){for(intj1;jm;j){cina[i][j];}}// 初始化备忘录为负无穷for(inti1;in;i){for(intj1;jm;j){f[i][j][0]f[i][j][1]-INF;}}// 从(n, m)出发终点(n,m)只能从上方或左边来不能从下方来// 所以分别计算k0和k1两种情况取最大值ll ansmax(dfs(n,m,0),dfs(n,m,1));coutansendl;return0;}功能分析模块功能说明三维备忘录f[N][N][2]存储每个位置在不同到达方向下的最大路径和用-INF表示未计算方向参数k区分从下方0还是从上方1到达当前点防止路径折返重复逆向DFS从(n, m)往(1, 1)搜索利用“从左边来”不依赖方向的性质简化状态转移边界处理出界返回 -INF不可能路径起点返回自身数值取最大值综合左边、上方、下方三个方向的来源选择最大路径正确性保证状态增加方向维度后路径不会重复经过同一个方格保证了无后效性记忆化确保每个(x, y, k)只计算一次时间复杂度 O(n×m×2) O(nm)。更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}