2022年“蓝桥杯”上海理工大学校选赛(重现赛)题解
本文最后更新于 382 天前,其中的信息可能已经有所发展或是发生改变。

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来求解。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
Source: https://github.com/zhaoolee/ChineseBQB
Source: https://github.com/zhaoolee/ChineseBQB
Source: https://github.com/zhaoolee/ChineseBQB
颜文字
Emoji
小恐龙
花!
滑稽大佬
演奏
程序员专属
上一篇
下一篇