摘花生

title: 题目
[摘花生 - OpenJ_Bailian 3727 - Virtual Judge (csgrandeur.cn)](https://vjudge.csgrandeur.cn/problem/OpenJ_Bailian-3727)
Hello Kitty 想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。Hello Kitty只能向东或向南走，不能向西或向北走。问Hello Kitty 最多能够摘到多少颗花生。
![[Pasted image 20220725151236.png]]
  
 
第一行是一个整数T，代表一共有多少组数据。1<=T <= 100  
接下来是T组数据。  
  
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C ( 1<= R,C <=100)  
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有 C 个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目 M ( 0<= M <= 1000)。
 
对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。

title: input
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
 
 

title: output
8
16
 

title: 思路
数字三角形模型基础用法：
**状态表示：** `f[i][j]` 在第i行第j列结束时总共所摘花生数
**状态属性：** max
**状态计算：** `f[i][j] = g[i][j] + max(f[i - 1][j], f[i][j - 1])`
从左边或者从上边转移过来。
 

title:代码
~~~ c ++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
long long g[N][N];
 
int main()
{
    int n, m, k;
    cin >> k;
    while (k--)
    {
        cin >> n >> m;
 
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                scanf("%d", &g[i][j]);
                g[i][j] += max(g[i - 1][j], g[i][j - 1]);
            }
        }
        cout << g[n][m] << endl;
    }
    return 0;
}
 
~~~