题解 P4611 【[COCI2011-2012#7] TRAMPOLIN】

姬小路秋子 · 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);
}