每日算法打卡:摘花生 day 14

发布时间:2024年01月14日

原题链接

1015. 摘花生

题目难度:简单

题目来源:《信息学奥赛一本通》

题目描述

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。

地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走,不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

1.gif

输入格式

第一行是一个整数T,代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有C个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式

对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。

数据范围

1≤T≤100,
1≤R,C≤100,
0≤M≤1000

输入样例:
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5 
输出样例:
8
16 

题目分析

这道题的意思就是要选择一条能摘到最多花生的数量的路线

对于这道题来说,我们依旧采用集合的思想来考虑,因为地图是二维的,所以我们考虑采用二位数组,f[i][j]他代表着走到第i,j位置的所有路线的最大值

从状态计算的角度来看,也就是集合划分,因为到达i,j的路线只有两种路线,一种是从i-1,j到i,j的位置,也就是从上到下,第二种就是从左到右走的

那么对于第i,j位置的结果就是

f ( i , j ) = max ? { f ( i ? 1 , j ) , f ( i , j ? 1 ) } + w i , j f(i,j)=\max\{f(i-1,j),f(i,j-1)\}+w_{i,j} f(i,j)=max{f(i?1,j),f(i,j?1)}+wi,j?

这里其实隐藏了一个初始化问题,就是边界情况,但是由于是要取最大值,恰好省略了,在其他DP问题是一定要分析初始化和边界问题的,其次是在递推的过程种,按照什么样的顺序计算呢,因为每一次算i,j时都需要知道之前的两个数值,这是可以画出一个有向图的,这里的顺序就是要按照拓扑序来计算,这道题按照数组遍历就恰好满足

示例代码

#include<iostream>
using namespace std;

const int N = 110;

int n,m;
int w[N][N];
int f[N][N];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>w[i][j];
            }
        }
        
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                f[i][j] = max(f[i-1][j],f[i][j-1]) + w[i][j];
            }
        }
        cout<<f[n][m]<<'\n';
    }
}
文章来源:https://blog.csdn.net/ye_yumo/article/details/135585575
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。