CF201C Fragile Bridges 题解

前言

题目链接

正解：动态规划

思路不是很好想，想出来了应该就没有多大问题了，但是需要处理的细节较多，~~再加上水水的样例~~，难度应该是偏难的。个人感觉应该是绿到蓝的亚子。

Update: 已经有评级了，绿的，针不戳。

先说说思路的来源

错误解法，不想看请跳过。

中午打开题目，第一反应：这不是一个暴搜部分分到手吗？

打了个无脑暴搜，深搜+回溯，分别向往左走和往右走的方向进行搜索，只是需要注意变量初始化和判断是否可以走。

时间复杂度 $Θ(2^{n})$，校内 OJ $15pts$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans,a[100005];
int dfs(int i,int sum){
    int left=sum,right=sum;
    if(!a[i-1]&&!a[i+1]) return sum;
    if(a[i-1]){ //可以往左走
        a[i-1]--; //要耗费一次桥的耐久度
        left=dfs(i-1,sum+1);
        a[i-1]++; //回溯
    }
    if(a[i+1]){ //可以往右走
        a[i+1]--; //要耗费一次桥的耐久度
        right=dfs(i+1,sum+1);
        a[i+1]++; //回溯
    }
    return max(left,right); //返回最大值
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n-1;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n-1;i++){
        ans=max(ans,dfs(i,0));
    }
    printf("%lld",ans);
    return 0;
}

~~可是 CF 的题都是绑在一个点上的啊~~，于是~~还没把正解想出来的~~我开始想怎么优化。

我先想到了一个假优化：使用一个前缀和 $pre$ 数组统计一下前面最多可能得多少分，如果现在得的分 + 往左/右走能拿到的最多的分都不可以更新答案的话就不用搜这一边了。

程序不做展示，但是我发现样例竟然没过……

淦，那到底是哪里出问题了呢？

经过短暂的思考我们可以发现，完全有这么一种可能：

假设你现在从第 $i$ 个平台往左走，在左边尽量赚到最多的分数之后回到第 $i$ 个平台，然后再往右边走，再在右边的平台结束游戏。

此时的得分完全是有可能高于 $pre_{i-1}+sum$ 或 $ans$ 的。

正解

上面的枝我们减错了，但是事情却有了一点眉目：

这道题好像每次的状态转移都与他离开之后回不回来有关系。

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

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

$dp_{i,0}$ 代表往左边走且不回来。
$dp_{i,1}$ 代表往左边走且必须回来。
$dp_{i,2}$ 代表往右边走且不回来。
$dp_{i,3}$ 代表往右边走且必须回来。

PS：关于必须回来这一个点，现有的题解说的是不保证回来，那么就有两种情况，较难判断。所以设置绝对一点较好思考。

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

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

然后再求从第 $i$ 个平台到第 $i-1$ 个平台能获得的最大分数。

首先要明确，我们是不回来的，所以最优的方式就是把这座桥尽量“榨干”，即能走断就走断，在两个平台之间反复横跳。但是若是要走到对面，需要走桥的次数必须是奇数。所以，如果桥当前还能走的最大次数是偶数，那就必须留一次走的机会（不然就走回去走不过来了）。

所以可以得出，往返这两个平台间能获得的最大分数（暂时叫 $score$）为：

$score= \begin{cases} a_{i-1},2\not\!|\;a_{i-1}\\ a_{i-1}-1,2\;|\;a_{i-1} \end{cases}$

在 c++ 中，我们可以用更加简洁的三目运算符表示。

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

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

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

$score= \begin{cases} a_{i-1}-1,2\not\!|\;a_{i-1}\\ a_{i-1},2\;|\;a_{i-1} \end{cases}$

同样可以用三目运算符解决。

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

不过这样还是不对，大家是否注意到这个程序没有关于无法走动的判断？现在这个判断来了！

如果这座桥能走的次数为 $1$，那我走过去这座桥就断了，无法回来。为此，我只能放弃前面的所有分数。

所以上述程序只有在 $a_i>1$ 时才能执行，当 $a_i=1$ 时，$dp_{i,1}$ 的值为 $0$（不用赋值）。

右边同理。只是循环要倒着枚举而已。

最后我们需要知道答案时什么。因为每一个平台都有可能作为出发点，所以需要枚举求解最优解。

那么，对于每一个点，我们可以先往左边走回来再往右边不回来，也可以先往右边回来再往左边不回来。所以答案就为：

$ans=\max_{i=1}^{n}\{dp_{i,0}+dp_{i,3},dp_{i,1}+dp_{i,2}\}$

提示：打代码的时候一定要注意你的这个下标到底代表的是平台还是桥！ 在这道题中，$dp$ 数组代表的是平台，$a$ 数组代表的是桥。

Code

#include<bits/stdc++.h>
using namespace std;
long long ans,n,a[100005],dp[100005][4];
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n-1;i++) scanf("%lld",&a[i]);
    for(int i=2;i<=n-1;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;i;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;
}

~~比暴力还短吼~~

提交记录作证 qwq：link

前言

先说说思路的来源

正解

Code​

Code