文章摘要
D Palace 链接： https://ac.nowcoder.com/acm/contest/23942/D 来源：牛客网 题目描述 在一个n×m大小的宫殿里面，每个坐标点 (i,j)(i∈[1,n],j∈[1,m])处都有一件价值为w的物品。 现在小明站在起点 (1,1)位置，他想走到目标点 (n,m)处，规定小明每次只能 向下 或者 向右 移动（不限移动次数）。 问：小明从起点移动到目标点…
D Palace 链接： https://ac.nowcoder.com/acm/contest/23942/D 来源：牛客网 题目描述 在一个n×m大小的宫殿里面，每个坐标点 (i,j)(i∈[1,n],j∈[1,m])处都有一件价值为w的物品。 现在小明站在起点 (1,1)位置，他想走到目标点 (n,m)处，规定小明每次只能 向下 或者 向右 移动（不限移动次数）。 问：小明从起点移动到目标点时总共可以拿走最多多少价值的物品，并输出该价值的大小。 输入描述: 第1行输入两个正整数n和m，表示宫殿的大小(1≤n,m≤100)。 第2-n+1行每行输入m个正整数wij(1≤i≤n,1≤j≤m)， 输入数据之间用空格隔开，wij表示坐标(i,j)处的物品价值 (1≤wij≤10^4) 输出描述: 输出答案。 示例1 输入 3 2 8 18 18 2 7 7 输出 40 这本是一道dp模板题，没什么难度，之所以记录下来的原因是我当初做这题的时候，意外的没有想到用dp，而是深搜，结果可以预料， Time Limit Exceeded DP思路 题目限定了只能向右或向下移动，那我只需要设计一个双层循环结构，并定义一个dp数组用来保存走到当前位置时的最大价值，然后在代码的最后输出终点对应的dp值，就是该题的答案了。 这么说了，表现得思路还是有点模糊，那尝试通过解析代码来进一步了解dp的解题思路。 DP代码 #include iostream> #include cstdio> using namespace std; unsigned int map 105] 105]; unsigned int dp 105] 105]; unsigned int m,n; int main() { cin >> n >> m; for(unsigned int i = 1; i = n; i++) { for(unsigned int j = 1; j = m; j++) { cin >> map j] i]; } } for(unsigned int y = 1; y = n; y++) { for(unsigned int x = 1; x = m; x++) { dp x] y] = max(dp x-1] y],dp x] y-1]) + map x] y]; } } cout dp m] n] endl; return 0; } 其实关键部分只有这一个循环语句块 for(unsigned int y = 1; y = n; y++) { for(unsigned int x = 1; x = m; x++) { dp x] y] = max(dp x-1] y],dp x] y-1]) + map x] y]; } } 循环遍历了 map ，并将当前的 map 值与上一步（左边或上边）的dp 最大值 作 和 ，并将 和 保存在 dp 中，表示从 起点 开始走到当前 坐标 的 最大价值和 。(dp初值都为0) 输出调试 sepline下面的是dp数组的值 其次是答案，通过数据，应该可以清晰地了解dp数组的作用。 3 2 8 18 18 2 7 7 ---Sep Line--- 8 26 26 28 33 40 40 3 3 18 3 18 18 0 18 3 0 18 ---Sep Line--- 18 21 39 36 36 57 39 39 75 75 TLE代码 #include iostream> #include cstdio> #include array> #include string> using namespace std; unsigned int map 101] 101]; unsigned int m,n; unsigned int ans; void dfs(unsigned int x, unsigned int y,unsigned int temp) { temp+=map x] y]; if(y==n x==m){ if(temp > ans) ans = temp; return; } if(y!=n) { dfs(x,y+1,temp); } if(x!=m) { dfs(x+1,y,temp); } } int main() { cin >> n >> m; for(unsigned int i = 1; i = n; i++) { for(unsigned int j = 1; j = m; j++) { cin >> map j] i]; } } dfs(1,1,0); cout ans endl; return 0; } 原因分析： 当m,n变大时，dfs递归就会反复走旧路线重新求和，影响效率，从而导致超时。 解决方法是使用记忆化搜索，减去一些不符号要求的路线，但是这样反而使得算法变得复杂，本题还是使用dp来求解。D Palace
题目描述
在一个n×m大小的宫殿里面，每个坐标点 (i,j)(i∈[1,n],j∈[1,m])处都有一件价值为w的物品。
现在小明站在起点 (1,1)位置，他想走到目标点 (n,m)处，规定小明每次只能向下或者向右移动（不限移动次数）。
问：小明从起点移动到目标点时总共可以拿走最多多少价值的物品，并输出该价值的大小。
输入描述:
第1行输入两个正整数n和m，表示宫殿的大小(1≤n,m≤100)。 第2-n+1行每行输入m个正整数wij(1≤i≤n,1≤j≤m)， 输入数据之间用空格隔开，wij表示坐标(i,j)处的物品价值 (1≤wij≤10^4)
输出描述:
输出答案。
示例1
输入
3 2<br> 8 18 <br> 18 2 <br> 7 7
输出
40
这本是一道dp模板题，没什么难度，之所以记录下来的原因是我当初做这题的时候，意外的没有想到用dp，而是深搜，结果可以预料，Time Limit Exceeded
DP思路
题目限定了只能向右或向下移动，那我只需要设计一个双层循环结构，并定义一个dp数组用来保存走到当前位置时的最大价值，然后在代码的最后输出终点对应的dp值，就是该题的答案了。
这么说了，表现得思路还是有点模糊，那尝试通过解析代码来进一步了解dp的解题思路。
DP代码
其实关键部分只有这一个循环语句块
循环遍历了map，并将当前的map值与上一步（左边或上边）的dp最大值作和，并将和保存在dp中，表示从起点开始走到当前坐标的最大价值和。(dp初值都为0)
输出调试
sepline下面的是dp数组的值
其次是答案，通过数据，应该可以清晰地了解dp数组的作用。
3 2<br> 8 18<br> 18 2<br> 7 7<br> ---Sep Line---<br> 8 26<br> 26 28<br> 33 40<br> 40
3 3<br> 18 3 18<br> 18 0 18<br> 3 0 18<br> ---Sep Line---<br> 18 21 39<br> 36 36 57<br> 39 39 75<br> 75
TLE代码
原因分析：
当m,n变大时，dfs递归就会反复走旧路线重新求和，影响效率，从而导致超时。
解决方法是使用记忆化搜索，减去一些不符号要求的路线，但是这样反而使得算法变得复杂，本题还是使用dp来求解。
本文采用 CC BY-NC-SA 4.0 协议进行授权，如无注明均为原创，转载请注明出处。
标题：2022年“蓝桥杯”上海理工大学校选赛（重现赛）题解作者：九仞之行链接：http://dev.styunlen.cn/archives/post-1310.html
还没有评论呢 ~ 快来抢沙发吧 🛋️