解决思路
设 \(dp[i][j]\) 表示第 \(i\) 行第 \(j\) 列所能去到的最大值，则有
- 当 \(j\) 列取值时
- \(dp[0][j]\) = 该列第一行的值 + 前一列第二行的值与前一列不取值时的最大值
- \(dp[1][j]\) = 该列第二行的值 + 前一列第一行的值与前一列不取值时的最大值
- 当 \(j\) 列不取值时
- 需要特别的标识为，令 \(dp[2][j]\) 表示当前列不取值时到第 \(j\) 列为止最大值
- 则有 \(dp[2][j] = max(dp[0][j - 1], dp[1][j - 1])\)
最后，取三者中的最大值即可
#include <bits/stdc++.h>
int main()
{
int n; std::cin >> n;
std::vector<std::vector<int>> team(2, std::vector<int>(n + 1, 0));
std::vector<std::vector<long long>> dp(3, std::vector<long long>(n + 1, 0));
for (int i = 0; i < 2; ++i) {
for (int j = 1; j <= n; ++j) {
std::cin >> team[i][j];
}
}
for (int col = 1; col <= n; ++col) {
dp[0][col] = std::max(dp[1][col - 1] + team[0][col], dp[2][col - 1] + team[0][col]);
dp[1][col] = std::max(dp[0][col - 1] + team[1][col], dp[2][col - 1] + team[1][col]);
dp[2][col] = std::max(dp[0][col - 1], dp[1][col - 1]);
}
std::cout << std::max(std::max(dp[0][n], dp[1][n]), dp[2][n]) << "\n";
return 0;
}
更好的解
利用滚动数组优化空间复杂度
#include <bits/stdc++.h>
int main()
{
int n; std::cin >> n;
std::vector<std::vector<int>> team(2, std::vector<int>(n + 1, 0));
std::vector<long long> dp(3, 0);
for (int i = 0; i < 2; ++i) {
for (int j = 1; j <= n; ++j) {
std::cin >> team[i][j];
}
}
for (int col = 1; col <= n; ++col) {
long long t0 = dp[0];
long long t1 = dp[1];
long long t2 = dp[2];
dp[0] = std::max(t1, t2) + team[0][col];
dp[1] = std::max(t0, t2) + team[1][col];
dp[2] = std::max(t0, t1);
}
std::cout << std::max(std::max(dp[0], dp[1]), dp[2]) << "\n";
return 0;
}