51nod 1083 矩阵取数问题

浅浅的花香味﹌ 2022-06-15 04:15 192阅读 0赞

[1083 矩阵取数问题][1083] ![ok.png][]

基准时间限制：1 秒 空间限制：131072 KB 分值: 5 [难度：1级算法题][1]

![star.png][] 收藏

![plus.png][] 关注

一个N\*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。

例如：3 \* 3的方格。

1 3 3

2 1 3

2 2 1

能够获得的最大价值为：11。

Input

第1行：N，N为矩阵的大小。(2 <= N <= 500)
    第2 - N + 1行：每行N个数，中间用空格隔开，对应格子中奖励的价值。（1 <= N[i] <= 10000)

Output

输出能够获得的最大价值。

Input示例

3
    1 3 3
    2 1 3
    2 2 1

Output示例

11

题目解析：

这是一道简单的dp题，动归方程: maxsum[i][j]=max(maxsum[i-1][j],maxsum[i][j-1])+D[i][j];

和这个题一样的还有hdu2089数塔题，可以去练练手。

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int maxsum[505][505],D[505][505];
    int main()
    {
        int T,i,j;
        scanf("%d",&T);
            for(i=0;i<T;i++)
                for(j=0;j<T;j++)
                    scanf("%d",&D[i][j]);
                    maxsum[0][0]=D[0][0];
                memset(maxsum,0,sizeof(maxsum));
                for(i=0;i<T;i++)
                    for(j=0;j<T;j++)
                    maxsum[i][j]=max(maxsum[i-1][j],maxsum[i][j-1])+D[i][j];
                printf("%d\n",maxsum[T-1][T-1]);
        return 0;
    }

[1083]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1083
[ok.png]: http://file.51nod.com/images/icon/ok.png
[1]: http://www.51nod.com/onlineJudge/problemList.html#!groupId=2
[star.png]: http://file.51nod.com/images/icon/star.png
[plus.png]: http://file.51nod.com/images/icon/plus.png

发表评论取消回复

表情：

评论列表（有 0 条评论，192人围观）

还没有评论，来说两句吧...

相关阅读

相关 51nod1230 幸运数 (数位dp）

[1230 幸运数][1230] ![ok.png][] 题目来源： [HackerRank][] [1230]: http://www.51nod.com/o

柔光的暖阳◎/ 2024年02月18日 18:31/ 0 赞/ 49 阅读

相关 51nod1016 水仙花数 V2

[1016 水仙花数 V2][1016 _ V2] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 160 [1016 _ V2]:

傷城~/ 2024年02月17日 22:56/ 0 赞/ 88 阅读

相关 51nod 1717 好数

有n个数 a\[1\],a\[2\],...,a\[n\]开始都是0 现在进行操作 t从1~n依次增加每次把下标时t的倍数的数都反转（0变成1,1变成0）如果最后a\

灰太狼/ 2024年02月17日 22:49/ 0 赞/ 20 阅读

相关 51nod 1084 矩阵取数问题 V2 dp

[1084 矩阵取数问题][1084] V2 基准时间限制：2 秒空间限制：131072 KB 分值: 80 [难度：5级算法题][5] 收藏关注一个M\N矩阵中

心已赠人/ 2024年02月17日 19:19/ 0 赞/ 90 阅读

相关 51nod 1002数塔取数 dp

一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。

不念不忘少年蓝@/ 2022年08月20日 13:11/ 0 赞/ 194 阅读

相关 51nod 1084+1083 矩阵取数问题 dp

先来说这个比较简单的问题：一个N\N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。例如：3 \ 3的

刺骨的言语ヽ痛彻心扉/ 2022年08月20日 12:26/ 0 赞/ 63 阅读

相关 51Nod--1002 数塔取数问题

因为5-31晚停电，所以6-1补上题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\!problemId=1

r囧r小猫/ 2022年06月15日 10:52/ 0 赞/ 229 阅读

相关 51nod 1083 矩阵取数问题

[1083 矩阵取数问题][1083] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 5 [难度：1级算法题][1] ![star.p

浅浅的花香味﹌/ 2022年06月15日 04:15/ 0 赞/ 193 阅读

相关 51Nod--1015 水仙花数

题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\!problemId=1015][http_www.51nod

小鱼儿/ 2022年06月14日 08:30/ 0 赞/ 212 阅读

相关 51nod1085背包问题

[51Nod - 1085][] [1085 背包问题][1085] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 0 [难度：

不念不忘少年蓝@/ 2022年05月22日 08:55/ 0 赞/ 162 阅读