CF201C 题解

zhou_ziyi · 2022-04-02 18:01:06 · 题解

题目大意

这个游戏包含 n 个平台，从左到右编号为 1 \sim n，相邻的两个平台间有一座桥。这些桥十分脆弱，游戏中会给出每座桥最多能走过的次数，第 i 座桥的次数为 a_i。如果走这座桥走了 a_i 次后这座桥就回断裂，再也不能走了。

游戏的过程是这样的：

• 首先找到一个起始的平台。

• 如果两边有桥，可以选择一边行走。如果走过一座桥之后走过的次数已经超过了 a_i，这座桥就会断裂。

• 如果当前所在的平台已经没有桥连接到另外任意一个平台，游戏结束。

在游戏结束时会计算分数。分数即为走过桥的次数。

请问最大的分数是多少？

题目分析

我们将第 i 与 i+1 个平台中的桥定义为 i 号桥，这也与输入的数组下标对应。

所以可以定义 dp 数组意义如下：

首先我们思考 dp_{i,0} 的情况。如果我们从第 i 个平台往左边走，就一定会走到第 i-1 个桥上。

我们的答案就因该为 ans=\max(dp_{i,0}+dp_{i,2},dp_{i,1}+dp_{i,3})

而因为不回第 i 个平台，所以我们无需考虑到了第 i-1 个平台后再往左走，还能不能回到第 i-1 的平台。因此，对于走到第 i-1 个平台能获得的最大分数，就为 dp_{i-1,0} 和 dp_{i-1,1} 的最大值。

我们是要不回来的，所以我们应该在这座桥中尽量多走几次，所以走的次数必须是奇数。

在 c++ 中我们可以这样写：

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + ((a[i - 1] & 1) ? a[i - 1] : (a[i - 1] - 1));

接着我们考虑 dp_{i,1}，如果要保证回到第 i 个平台，那么必须保证要先回到第 i-1 个平台，然后还要能从中间那座桥走过去。所以前面加上的是 dp_{i-1,1}，没有别的情况。

为了拿到最大分数，我们要像之前一样，因为要回去，我们需要经过偶数次桥。如果当前桥能走的次数是奇数，那就只能浪费一次机会达到能回来的目的。

在 c++ 中我们可以这样写：

dp[i][1] = dp[i - 1][1] + ((a[i - 1] & 1) ? (a[i - 1] - 1) : a[i - 1]);

而 dp_{i,2} 和 dp_{i,3} 同理，不做赘述。

Code

#include <cstdio>
#include <iostream>
#define ll long long
using namespace std;
const int MAXN = 1e5 + 5;
ll ans;
ll n, a[MAXN], dp[MAXN][4];
int main() {
    scanf("%lld", &n);
    for(int i = 1; i < n; i++)
        scanf("%lld", &a[i]);
    for(int i = 2; i <= n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + ((a[i - 1] & 1) ? a[i - 1] : (a[i - 1] - 1));
        if(a[i - 1] > 1)
            dp[i][1] = dp[i - 1][1] + ((a[i - 1] & 1) ? (a[i - 1] - 1) : a[i - 1]);
    }
    for(int i = n - 1; i >= 1; i--) {
        dp[i][2] = max(dp[i + 1][2], dp[i + 1][3]) + ((a[i] & 1) ? a[i] : (a[i] - 1));
        if(a[i] > 1)
            dp[i][3] = dp[i + 1][3] + ((a[i] & 1) ? (a[i] - 1) : a[i]);
    }
    for(int i = 1; i <= n; i++)
        ans = max(ans, max(dp[i][0] + dp[i][3], dp[i][1] + dp[i][2]));
    printf("%lld", ans);
    return 0;
}