CF-1195C Basketball Exercise 题解

题目大意

给你两个序列a和b，你可以从中任意选取其中的数字，但是你不能取相邻的两个数字，问所取的数字的最大和。

解题思路

典型的线性DP题。。

但是写的DP题少啊。。DP还是相当苦手。

需要多刷点题。。不过最近没啥时间，要期末考了。。等暑假吧。

我们可以用$dp[i][j][h]$来表示第i列到序列最右端的最大和，其中j代表第几行，h代表这一位取或者而不取。

那么我们便可以得到状态转移方程。

假如我第i位不取，那么无论是第1行，还是第2行，都是右边所有情况的最大值，因为我这一位不取，不会影响到后面的取舍，所以只需要取其中的最大值即可。

$dp[i][1][0] = dp[i][2][0] = max(max(dp[i + 1][1][0], dp[i + 1][1][1]), max(dp[i + 1][2][0], dp[i + 1][2][1]))$

假如我第i位取，那么对第一行来说，我不能取第一行后面相邻的那个数，但是对第二行的取舍是没有影响的，所以取这三种情况的最大值并且加上该位上的值即可。

$dp[i][1][1] = max(dp[i + 1][1][0], max(dp[i + 1][2][0], dp[i + 1][2][1])) + num[i][1]$

对于第二行来说是类似的，我不能取第二行后面相邻的那个数，但是对第一行的取舍是没有没有影响的，所以也是取这三种情况的最大值加上该位上的值即可。

$dp[i][2][1] = max(dp[i + 1][2][0], max(dp[i + 1][1][0], dp[i + 1][1][1])) + num[i][2]$

但是需要注意，我们需要从右边开始倒序转移，因为重叠的子问题都是与右边的情况有关的。

最后的结果就是第一列中第一行取或不取，第二行取或不取四种情况中的最大值。

即$max(max(dp[1][1][0], dp[1][1][1]), max(dp[1][2][0], dp[1][2][1]))$。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5+5;
typedef long long ll;
ll dp[N][3][2],num[N][3];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)	cin>>num[i][1];
	for (int i = 1; i <= n; i++)	cin>>num[i][2];
	for (int i = n; i >= 1; i--) {
		dp[i][1][0] = dp[i][2][0] = max(max(dp[i + 1][1][0], dp[i + 1][1][1]), max(dp[i + 1][2][0], dp[i + 1][2][1]));//这一位没取的情况
		dp[i][1][1] = max(dp[i + 1][1][0], max(dp[i + 1][2][0], dp[i + 1][2][1])) + num[i][1];//这一位第1行取了的情况
		dp[i][2][1] = max(dp[i + 1][2][0], max(dp[i + 1][1][0], dp[i + 1][1][1])) + num[i][2];//这一位第2行取了的情况
	}
	cout << max(max(dp[1][1][0], dp[1][1][1]), max(dp[1][2][0], dp[1][2][1])) << endl;
}