题解出处：https://www.luogu.org/problemnew/solution/CF1195C

很水的一道C题……目测难度在黄~绿左右。请各位切题者合理评分。

注意到可以选择的球员编号是严格递增的，因此可以把状态的第一维定义为球员编号，第二维描述编号同为 ii 的两名球员的选取情况。

定义状态：f[i][0/1/2]f[i][0/1/2] 表示选取了编号在 ii 及以前的球员，所能得到的身高总和最大值。其中，第二维的 00 表示编号为 ii 的球员一个都不选；11 表示只选上面一个；ii 表示只选下面一个。（显然没有上下都选的情况）

状态转移方程：

f[i][0]=max{f[i−1][0],f[i−1][1],f[i−1][2]}f[i][1]=max\lbrace f[i-1][0],f[i-1][2]\rbrace+height[i][1]f[i][1]=max{f[i−1][0],f[i−1][2]}+height[i][1]f[i][2]=max\lbrace f[i-1][0],f[i-1][1]\rbrace+height[i][2]f[i][2]=max{f[i−1][0],f[i−1][1]}+height[i][2]

Update: 用贪心可以证明，在最优解中，不会出现连续两列一个不取的情况。因此， f[i][0]f[i][0] 其实没有必要考虑来自 f[i-1][0]f[i−1][0] 的状态转移。

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
ll h[100005][3];
ll f[100005][3];
int main() {
    cin >> N;
    for (register int i = 1; i <= N; ++i) cin >> h[i][1];
    for (register int i = 1; i <= N; ++i) cin >> h[i][2];
    f[1][0] = 0;
    f[1][1] = h[1][1];
    f[1][2] = h[1][2];
    for (register int i = 2; i <= N; ++i) {
        f[i][0] = max(f[i - 1][0], max(f[i - 1][1], f[i - 1][2]));
        f[i][1] = max(f[i - 1][0], f[i - 1][2]) + h[i][1];
        f[i][2] = max(f[i - 1][0], f[i - 1][1]) + h[i][2];
    }
    cout << max(f[N][0], max(f[N][1], f[N][2]));
    return 0;
}

 

版权声明：本文为YY666原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/YY666/p/11238715.html