题目描述

难度分:$1400$

输入$n(1 \leq n \leq 10^5)$和一个$2$行$n$列的矩阵$a(1 \leq a[i][j] \leq 10^9)$。

你需要从矩阵中选择一些数，要求任意两数不能左右相邻，也不能上下相邻。

输出所选数字之和的最大值。

输入样例$1$

5
9 3 5 7 3
5 8 1 4 5

输出样例$1$

29

输入样例$2$

3
1 2 9
10 1 1

输出样例$2$

19

输入样例$3$

1
7
4

输出样例$3$

9

算法

动态规划

状态定义

利用二进制状态压缩的思想，用$0$表示某一列没有选数，用$1$表示选了第$1$行的数，用$2$表示选了第$2$行的数。而所选的数不能上下相邻，所以不存在一列中两个数都选的情况，只有这三种状态。用$f[i][0/1/2]$表示第$i$列状态为$0/1/2$时，列$[1,i]$上所选数的最大和，显然在这种状态下，答案就是$max_{mask=0}^{2}f[n][mask]$。

状态转移

1. 当第$i$列状态为$0$时，前一列是什么状态都无所谓，状态转移方程为$f[i][0]=max(f[i-1][0],f[i-1][1],f[i-1][2])$；
2. 当第$i$列状态为$1$时，前一列只能是$0$或$2$的状态，状态转移方程为$f[i][1]=max(f[i-1][0],f[i-1][2])$；
3. 当第$i$列状态为$2$时，前一列只能是$0$或$1$的状态，状态转移方程为$f[i][2]=max(f[i-1][0],f[i-1][1])$。

复杂度分析

时间复杂度

状态数量为$3n$，单次转移的时间复杂度为$O(1)$，因此整体就是一个普通的线性DP，时间复杂度为$O(n)$。

空间复杂度

空间的消耗就是DP数组$f_{n \times 3}$，额外空间复杂度为$O(n)$（由于每一列的状态只依赖于前一列的状态，因此可以通过滚动数组优化成$O(1)$）。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 100010;
int a[2][N], n;
LL f[N][4];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[0][i]);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[1][i]);
    }
    for(int i = 1; i <= n; i++) {
        f[i][0] = max(f[i - 1][0], max(f[i - 1][1], f[i - 1][2]));     // 第i列不选数
        f[i][1] = max(f[i - 1][0], f[i - 1][2]) + a[0][i];             // 第i列选第一行的数
        f[i][2] = max(f[i - 1][0], f[i - 1][1]) + a[1][i];             // 第i列选第二行的数
    }
    printf("%lld\n", max(f[n][0], max(f[n][1], f[n][2])));
    return 0;
}