CF201C Fragile Bridges TJ

本题解依旧发布于洛谷,如果您能点个赞的话……(逃

前言

题目链接

正解:动态规划

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


先说说思路的来源(错误解法,不想看请跳过)

中午打开题目,第一反应:这不是一个暴搜部分分到手吗?

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

时间复杂度 \(Θ(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++ 中,我们可以用更加简洁的三目运算符表示。

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} \]

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

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

上一篇:AT4828 [ABC152D] Handstand 2 TJ


下一篇:TJ Holowaychuk是怎样学习编程的?