Решение задачи "Прыгающая лягушка" с Codeforces

Без пояснения   Просмотров: 11

Слева от строки s=s1s2…sn, состоящей из n символов, находится лягушка (точнее, изначально лягушка находится в клетке 0). Каждый символ строки s — это или 'L', или 'R'. Это значит, что если лягушка находится в i-й клетке и i-й символ — это 'L', то она может прыгать только влево. Если лягушка стоит в i-й клетке и i-й символ — это 'R', то она может прыгать только вправо. Из клетки 0 лягушка может прыгать только вправо.

Заметим, что лягушка может прыгать в одну и ту же клетку дважды и может совершить столько прыжков, сколько ей потребуется.

Лягушка хочет достичь n+1-й клетки. Лягушка выбирает некоторое целое положительное значение d перед самым первым прыжком (и потом не может изменить его) и прыгает не более, чем на d клеток за раз. То есть, если i-й символ — 'L', то лягушка может прыгнуть в любую клетку из отрезка [max(0,i−d);i−1], а если i-й символ — 'R', то лягушка может прыгнуть в любую клетку из отрезка [i+1;min(n+1;i+d)].

Лягушка не хочет прыгать слишком далеко, поэтому ваша задача — найти минимальное возможное значение d, при котором лягушка сможет достичь клетки n+1 из клетки 0, если будет прыгать не более, чем на d клеток за раз. Гарантируется, что всегда возможно достичь n+1 из 0.

Вам нужно ответить на t независимых наборов входных данных.

Код 

#include<bits/stdc++.h>
using namespace std;

int main(){
	int T;
	cin>>T;
	while(T--){
		string str;
		cin>>str;
		str="R"+str+"R";
		int pre=0,maxn=0;
		for(int i=1;i<str.length();i++)
			if(str[i]=='R'){
				maxn=max(maxn,i-pre);
				pre=i;	
			}
		cout<<maxn<<endl;
	}
	return 0;
}

         

Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться