Contest 1786 - 2019 년 2 단계 나 강해 질 래 개인 트 레이 닝 10 차 전 문제 A: Kenken Race dp 추월

제목 링크:http://icpc.upc.edu.cn/problem.php?cid=1786&pid=0
제목 설명
There are N squares arranged in a row, numbered 1,2,...,N from left to right. You are given a string S of length N consisting of . and #. If the i-th character of S is #, Square i contains a rock; if the i-th character of S is ., Square i is empty. In the beginning, Snuke stands on Square A, and Fnuke stands on Square B. You can repeat the following operation any number of times: Choose Snuke or Fnuke, and make him jump one or two squares to the right. The destination must be one of the squares, and it must not contain a rock or the other person. You want to repeat this operation so that Snuke will stand on Square C and Fnuke will stand on Square D. Determine whether this is possible. Constraints 4≤N≤200000 S is a string of length N consisting of . and #. 1≤A,B,C,D≤N Square A, B, C and D do not contain a rock. A, B, C and D are all different. A A B
 
입력
Input is given from Standard Input in the following format: N A B C D S
 
 
출력
Print Yes if the objective is achievable, and No if it is not.
 
샘플 입력
샘플 데이터 복사

7 1 3 6 7
.#..#..

샘플 출력

Yes

문제 풀이: 만약 c = = d 는 틀림없이 안 될 것 이다. 만약 cd 라면 두 번 째 방법 처럼 달 려 갈 수 있 는 지, 만약 안 된다 면 중간 에 a 가 차 를 추월 할 수 있 는 지, 추월 의 조건 은 적어도 세 개의 공 터 를 연속 하 는 것 이다.

#include

using namespace std;

typedef long long ll;
const int N = 200100;

char s[N];
int dp[N];
int n;
int a, b, c, d;
int main() {

	while(~scanf("%d %d %d %d %d", &n, &a, &b, &c, &d)) {
		scanf("%s", s + 1);
		if( c == d ) {
			printf("No
");
			continue;
		}
		for(int i = 0; i <= n; i++) dp[i] = 0;
		if(c < d) {
			dp[b] = 1;
			for(int i = b + 1; i <= d; i++) {
				if(s[i] == '#' ) continue;
				dp[i] = dp[i - 1] | dp[i - 2];
			}
			if(!dp[d]) {
				printf("No
");
				continue;
			}
			for(int i = 0; i <= n; i++) dp[i] = 0;
			dp[a] = 1;
			for(int i = a + 1; i <= c; i++) {
				if(s[i] == '#' || i == d) continue;
				dp[i] = dp[i - 1] | dp[i - 2];
			}
			if(!dp[c]) {
				printf("No
");
				continue;
			}
			printf("Yes
");
		} else {
			dp[b] = 1;
			for(int i = b + 1; i <= d; i++) {
				if(s[i] == '#' ) continue;
				dp[i] = dp[i - 1] | dp[i - 2];
			}
			if(!dp[d]) {
				printf("No
");
				continue;
			}
			for(int i = 0; i <= n; i++) dp[i] = 0;
			dp[a] = 1;
			for(int i = a + 1; i <= c; i++) {
				if(s[i] == '#' || i == d) continue;
				dp[i] = dp[i - 1] | dp[i - 2];
			}
			if(dp[c]) {
				printf("Yes
");
				continue;
			}
			for(int i = 0; i <= n; i++) dp[i] = 0;
			dp[a] = 1;
			for(int i = a + 1; i <= c; i++) {
				if(s[i] == '#' ) continue;
				dp[i] = dp[i - 1] | dp[i - 2];
			}
			int flag = 0;
			for(int i = b - 1; i <= d- 2; i++) {
				if(s[i] == '.' && s[i + 1] == '.' && s[i + 2] == '.')
					flag = 1; 
			}
			printf(dp[c] && flag ? "Yes
" : "No
");
		}
		
	}

	return 0;
}