方格取数[CSP-J2_2020]

admin

[color=rgba(0, 0, 0, 0.75)]

设有 n \times mn×m 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。

输入格式[color=rgba(0, 0, 0, 0.75)]

第一行有两个整数 n, mn,m。

接下来 nn 行每行 mm 个整数，依次代表每个方格中的整数。

输出格式[color=rgba(0, 0, 0, 0.75)]

一个整数，表示小熊能取到的整数之和的最大值。

admin

f[j][→]]（f[j][0]f[j][0]） 表示从当前格子的左边走到当前格子能取到的最大整数之和。
f[j][f[j][↓]] （f[j][1]f[j][1]） 表示当前格子的上边走到当前格子能取到的最大整数之和。
f[j][f[j][↑]] （f[j][2]f[j][2]） 表示当前格子的下边走到当前格子能取到的最大整数之和。

先进行第 11 列的填值。
因为其处在整个地图的最左侧，所以只有 ↓ 方向是可以取到格子里的数的（如果向上走，最后必将无路可走）。
f[1][1] = f[i-1][1][1] + a[1]
然后再进行第 2 ~ m 列的填值。
先填 → 方向及 ↓ 方向的值，再从下往上填 ↑ 方向的值。

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. #define ll long long
   
4. #define inf -1e17
   
5. ll f[1005][1005][3];
   
6. ll a[1005][1005];
   
7. int n,m;
   
8. ll maxx(ll a,ll b)
   
9. {
   
10.     return a>b ?a :b;
    
11. }
    
12. int main()
    
13. {
    
14.     cin>>n>>m;
    
15.     for(int i=1;i<=n;i++)
    
16.     {
    
17.         for(int j=1;j<=m;j++)
    
18.         {
    
19.             cin>>a[i][j];
    
20.             f[i][j][0] = inf;
    
21.             f[i][j][1] = inf;
    
22.             f[i][j][2] = inf;
    
23. 
    
24.         }
    
25.     }
    
26.     f[1][1][0]=a[1][1];
    
27.     f[1][1][1]=a[1][1];
    
28.     f[1][1][2]=a[1][1];
    
29.     for(int i=2;i<=n;i++)
    
30.     {
    
31.         f[i][1][1] = f[i-1][1][1] + a[i][1];
    
32.     }
    
33.     for(int j=2;j<=m;j++)
    
34.     {
    
35.         for(int i=1;i<=n;i++)
    
36.         {
    
37.             f[i][j][0]=maxx(f[i][j-1][1],maxx(f[i][j-1][0],f[i][j-1][2]))+a[i][j];
    
38.             if(i>=2) f[i][j][1]=maxx(f[i-1][j][0],f[i-1][j][1])+a[i][j];  //↓方向
    
39.         }
    
40.         for(int i=n-1;i>=1;i--)  //↑方向
    
41.         {
    
42.             f[i][j][2]=maxx(f[i+1][j][0],f[i+1][j][2])+a[i][j];
    
43.         }
    
44.     }
    
45.     cout<<maxx(f[n][m][0],maxx(f[n][m][1],f[n][m][2]));
    
46.     return 0;
    
47. }

复制代码