【每日一题21】AcWing 1015. 摘花生

发表于 更新于 Valine：
本文字数： 100 阅读时长 ≈ 1 分钟

Day21 AcWing 1015. 摘花生

思路

  1. dp
  2. 滚动数组，单数&1就是用数组第1行，双数就是第2行
    3&1=1,2&1=0

代码

算法1 dp $O(n^2)$
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
#include<iostream>
using namespace std;

const int N = 105;
int a[N][N], f[N][N];
int q, row, col;

int main()
{
    cin >> q;
    while(q--){
        cin >> row >> col;
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                cin >> a[i][j];
            }
        }

        // f[i][j]指的是到(i, j)的最大花生数
        for(int i = 1; i <= row; i++){
            for(int j = 1; j <= col; j++){
                f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j];
            }
        }

        cout << f[row][col] << endl;
    }

    return 0;
}
算法2 滚动数组，$O(n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstring>
#include<iostream>
using namespace std;

const int N = 105;
int a[2][N], f[2][N], q, n, m;

int main()
{
    cin >> q;
    while(q--){
        cin >> n >> m;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cin >> a[i&1][j];
                f[i&1][j] = max(f[i&1][j-1], f[(i-1)&1][j]) + a[i&1][j];
            }
        }
        cout << f[n&1][m] << endl;

        memset(f, 0, sizeof f);
    }
}