레이팅 미적용농부 존의 \(N\)마리 소들(\(2 \leq N \leq 3\cdot 10^5\))은 여느 때처럼 \(1 \ldots N\)의 번호가 붙어 있으며, \(1\ldots N\)의 순열 \(p_1,p_2,\ldots,p_N\)에 따라 줄을 서 있다. 또한 문자 U와 D로 이루어진 길이 \(N-1\)의 문자열이 주어진다. 모든 \(1\le j\le K\)에 대해, 문자열의 \(j\)번째 문자가 U이면 \(a_{j - 1} < a_j\)이고, D이면 \(a_{j - 1} > a_j\)인 \(p\)의 부분 수열 \(a_0,a_1,\ldots,a_{K}\)가 존재하는 최대의 \(K\le N-1\)을 구하시오.
출제: Danny Mittal
배점
- 테스트 케이스 3-4는 \(N\le 500\)을 만족한다.
- 테스트 케이스 5-8은 \(N\le 5000\)을 만족한다.
- 테스트 케이스 9-12에서는 문자열이 U들 뒤에 D들이 오는 형태이다.
- 테스트 케이스 13-22는 추가 제약이 없다.
출제: Danny Mittal
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 \(p_1,p_2,\ldots,p_N\)이 주어진다.
마지막 줄에 문자열이 주어진다.
가능한 \(K\)의 최댓값을 출력한다.
5
1 5 3 4 2
UDUD4We can choose \([a_0,a_1,a_2,a_3,a_4]=[p_1,p_2,p_3,p_4,p_5]\); the entire
permutation is consistent with the string.
5
1 5 3 4 2
UUDD3We can choose \([a_0,a_1,a_2,a_3]=[p_1,p_3,p_4,p_5]\).
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > US Open > Platinum