P4611 [COCI2011-2012#7] TRAMPOLIN

时间：2023-03-09 14:47:14
P4611 [COCI2011-2012#7] TRAMPOLIN

题目背景

有很多超级英雄：蝙蝠侠，蜘蛛侠，超人等。其中，有一位叫牛。今天他想模仿蜘蛛侠，所以他选择了一排高大的摩天楼来跳。

题目描述

具体而言，他选择了一个由 N 个摩天大楼构成的序 列，从左到右编号从 1 到 N.他最初位于第 K 座摩天大厦。不幸的是，这样的他的能力有限，所以只能向左或向右跳到相邻的摩天楼，只有那些摩天大楼的高度不大于他目前的摩天大楼 的高度的楼房才行。然而，他使蹦床上一些摩天大楼，从这些摩天大厦，他可以跳到任何其 他的摩天大楼，无论多么高以及位置在何处。 找出从第 K 座楼房开始，他能跳到的最多的不同的楼房数。如果一个楼房被多次访问，我 们只计算一次。楼房 K 也被计算在内，不管我们是否回到过楼房 K。

输入输出格式

输入格式：

第一行，包含两个数Ｎ和 K (3 ≤ N ≤ 300 000, 1 ≤ K ≤ N)，表示楼房总数和开始的楼
房。
第二行Ｎ个数，均小于 10^6，从左到右依次表示楼房的高度。
第三行Ｎ个字符'.' 或'T'.如果第 i 个字符是'T'，表示这里有一个蹦床在第 i 个楼房。

输出格式：

一个数，有示最多能到的楼房数。

输入输出样例

输入样例#1： 
6 4

12 16 16 16 14 14

.T....
输出样例#1： 
5
输入样例#2： 
10 1

10 7 3 1 1 9 8 2 4 10

..T..T....
输出样例#2： 
7

说明

样例 2 线路如下： 1 –>2 –>3 –>6 –>10 –>9 –>8.

Solution：

　　本题贪心+模拟。

　　从一个位置出发，要么先往左走，要么先往右走，我们分别递推处理出每个点往左和往右能访问的最多的点数，同时对于能到达有$T$位置的点，等价于当前位置也能到任意点，于是把它的位置也标记为$T$。

　　然后分情况讨论：

　　若第$k$位位置为$T$，那么统计$T$的个数，并记录非$T$位置向左或向右能到达的最多点数，答案就是两者累加（注意：不必考虑两者有重复点的情况，因为我们对于能到达$T$的点都标记为$T$了）。

　　若第$k$位位置不为$T$，因为等高可以互达，那么先统计与$k$等高的位置最多往两边扩展多少，答案就是扩展的长度+两边界分别向左向右能到达的最多点数。

代码：

/*Code by 520 -- 9.5*/

#include<bits/stdc++.h>

#define il inline

#define ll long long

#define RE register

#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)

#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)

using namespace std;

const int N=;

int n,k,h[N],lf[N],rt[N],maxn[N];

char t[N];

int main(){

    scanf("%d%d",&n,&k);

    For(i,,n) scanf("%d",h+i);

    scanf("%s",t+);

    For(i,,n) if(h[i]>=h[i-]){

        if(t[i-]=='T')t[i]='T';

        lf[i]=lf[i-]+;

    }

    Bor(i,,n-) if(h[i]>=h[i+]){

        if(t[i+]=='T')t[i]='T';

        rt[i]=rt[i+]+;

    }

    int T=,best=;

    For(i,,n)

        if(t[i]=='T')++T;

        else best=max(best,max(lf[i],rt[i])+);

    if(t[k]=='T')printf("%d\n",T+best),exit();

    int l=k,r=k;

    while(l>&&h[l-]==h[k])l--;

    while(r<n&&h[r+]==h[k])r++;

    printf("%d\n",r-l++max(lf[l],rt[r]));

    return ;

}

相关文章