自动搬运

查看原文

来自洛谷，原作者为

	姬小路秋子 **

搬运于2025-08-24 22:01:56，当前版本为作者最后更新于2018-06-13 09:35:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题的思路很精妙。

先考虑初始点无法跳到任何一个蹦床上去，那么这种情况的最大楼房数就只能是与它相邻的连续左边或右边一段数，这个判断一下就好了。

再来考虑初始点能跳到蹦床上去。

我们发现，如果某一个点可以跳到蹦床，那么相当于这个楼房也是一个蹦床（跳着跳着就能去一个蹦床了）。于是我们把与蹦床可以跳到的位置全都改成蹦床，因为初始点可以去蹦床（也就是可以跳到任何一个地方），那么这些与蹦床相邻的点都可以被跳到。那么跳完了所有与蹦床相邻的点后怎么办？再找一段最大的没有与蹦床相邻的点跳过去，这些就是答案。

代码：

#include<bits/stdc++.h>
using namespace std;
char s[500001];
int n,m,i,l,r,ans,a[500001],rs[500001],ls[500001],sum;
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	scanf("%s",&s);
	for(i=2;i<=n;i++)
	 if(a[i]>=a[i-1]){
	 	ls[i]=ls[i-1]+1;
	 	if(s[i-2]=='T')s[i-1]='T';
	 }
	for(i=n-1;i;i--)
	 if(a[i]>=a[i+1]){
	 	rs[i]=rs[i+1]+1;
	 	if(s[i]=='T')s[i-1]='T';
	 } 
	/*for(i=1;i<=n;i++)printf("%d ",ls[i]);
	puts("");
	for(i=1;i<=n;i++)printf("%d ",rs[i]);
	puts(""); 
	printf("%s\n",s);*/
	if(s[m-1]=='T'){
		for(i=1;i<=n;i++){
			if(s[i-1]=='T')ans++;
			 else sum=max(sum,max(ls[i],rs[i])+1);
		}
		printf("%d",ans+sum);
		return 0;
	} 
	l=r=m;
	while(l>1&&a[l-1]==a[l])l--;
	while(r<n&&a[r+1]==a[r])r++;
	printf("%d",max(ls[r],rs[l])+1);
}