AcWing1015.摘花生

题目描述

$HelloKitty$想摘点花生送给她喜欢的米老鼠。

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

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

$HelloKitty$只能向东或向南走，不能向西或向北走。

问$HelloKitty$最多能够摘到多少颗花生。

输入格式

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

接下来是T组数据。

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

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

输出格式

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

数据范围

$1\le T\le 100,$
$1\le R,C\le 100,$
$0\le M\le 1000$

输入样例：

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

输出样例：

8
16

算法

动态规划

定义：定义$f[i,j]$为从$(1,1)$走到$(i,j)$可以摘到的最大花生数量

状态转移：因为每次可以向右边走，向下面走，所以我们把这个状态划分为两种（按前一步的操作划分），一种是从左边走过来（向右），另一种是从上面走过来（向下）。

因为从左走的最大花生数为$f(i,j-1)$，从上走的最大花生数为$f(i-1,j)$，这两个取$Max$就得到上一步的最大值，然后再加上本格的花生数量就行了。得出以下的状态转移方程

$f\left(i,j\right)=\max \left(f\left(i,j-1\right),f\left(i-1,j\right)\right)$,得出代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
int f[N][N], t;

int read() {
    int x = 0, f = 1; char c = getchar();
    for(; !isdigit(c); c = getchar()) f = (c == '-') ? -1 : 1;
    for(;  isdigit(c); c = getchar()) x = x * 10 + c - 48;
    return x * f;
}

int main()
{
    t = read();
    while (t -- )
    {
        int n = read(), m = read();
        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]) + read();
        printf("%d\n", f[n][m]);
    }
    return 0;
}

这个在提高课中被分到了“数字三角形模型”，那他和数字三角形的相似处在哪里？
都是线性dp，都是从两个地方转移过来，甚至状态转移方程完全一样(循环不一样)，所以要举一反三，融会贯通。