E2-B 矩阵移动

题目描述

给定一个 n×mn×m 的矩阵，初始位于$ (1,1)$ ，目标位置为 (n,m)(n,m)，每次可以向下移动或向右移动，即从 (x,y)(x,y) 移动到 (x+1,y)(x+1,y) 或 (x,y+1)(x,y+1)，但不能移动到矩阵之外。

祂想知道经过位置元素之和的最大值是多少。

输入格式

第一行一个正整数 t（1≤t≤5）t（1≤t≤5），表示数据组数。

对于每组数据，第一行两个正整数 n,m（2≤n,m≤103）n,m（2≤n,m≤10^3），含义同题目描述。

接下来 nn 行，第 i（1≤i≤n）i（1≤i≤n）行 mm 个整数 ai,1,ai,2,…,ai,m（−109≤ai,j≤109）a_{i,1},a_{i,2},…,a_{i,m}（−10^9≤a_{i,j}≤10^9），含义同题目描述。

输出格式

对于每组数据，输出一行一个整数，表示经过位置元素之和的最大值。

输入样例

1
2
3
4
5
6
7
8
9
2
3 3
1 2 3
4 5 6
7 8 9
3 3
1 -1 1
2 -2 2
3 -3 3

输出样例

1
2
29
6

题目分析

对于当前格子(x,y)(x,y)，他的上一个状态只有可能是(x−1,y)(x-1,y)或(x,y−1)(x,y-1)，所以假设当前格子为最优路线，则到达此格子的结果dp[x][y]dp[x][y]应为：

dp[x][y]=max(dp[x−1][y],dp[x][y−1])+a[x][y]dp[x][y]=max(dp[x-1][y],dp[x][y-1])+a[x][y]

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<stdio.h>
long long a[1100][1100];
long long dp[1100][1100];
int main()
{
   	int t;
    scanf("%d",&t);
    while(t--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= m; k++)
            {
                ans[j][k] = 0;
                scanf("%lld", &a[j][k]);
            }
        }
        ans[1][1] = a[1][1];
        for (int j = 2; j <= n; j++)
        {
            ans[j][1] = ans[j - 1][1] + a[j][1];
        }
        for (int j = 2; j <= m; j++)
        {
            ans[1][j] = ans[1][j - 1] + a[1][j];
        }
        for (int j = 2; j <= n; j++)
        {
            for (int k = 2; k <= m; k++)
            {
                ans[j][k] = a[j][k] + (ans[j - 1][k] > ans[j][k - 1] ? ans[j - 1][k] : ans[j][k - 1]);
            }
        }
        printf("%lld\n", ans[n][m]);
    }
    return 0;
}