首页 > 代码库 > UVa 11661 - Burger Time?

UVa 11661 - Burger Time?

题目:给你一个长度是n的字符串,判断距离最近的R和D见得距离,如果有Z输出0。

分析:dp,简单dp。直接从两个方向找到每个R前面最近的D即可。

说明:简单题。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

char way[2000002]; 

int main()
{
	int n;
	while (scanf("%d",&n) && n) {
		scanf("%s",way);
		
		int D = -2000002,Max = 2000002;
		for (int i = 0 ; i < n ; ++ i) {
			if (way[i] == 'D') D = i;
			if (way[i] == 'R') Max = min(Max, i-D);
			if (way[i] == 'Z') Max = 0;
		}
		D = 4000002;
		for (int i = n-1 ; i >= 0 ; -- i) {
			if (way[i] == 'D') D = i;
			if (way[i] == 'R') Max = min(Max, D-i);
		}
		
		printf("%d\n",Max);	
	}
    return 0;
}


UVa 11661 - Burger Time?