#PU1238. USACO 2022 US Open Contest, Platinum — Problem 3. Up Down Subsequence

USACO 2022 US Open Contest, Platinum — Problem 3. Up Down Subsequence

USACO 2022 US Open Contest, Platinum — Problem 3. Up Down Subsequence

题目描述

Farmer John's NN cows (2≤N≤3⋅1052 \leq N \leq 3\cdot 10^5), conveniently numbered 1…N1 \ldots N as usual, have ordered themselves according to a permutation p1,p2,…,pNp_1,p_2,\ldots,p_N of 1…N1\ldots N. You are also given a string of length N−1N-1 consisting of the letters U and D. Please find the maximum K≤N−1K\le N-1 such that there exists a subsequence a0,a1,…,aKa_0,a_1,\ldots,a_{K} of pp such that for all 1≤j≤K1\le j\le K, aj−1<aja_{j - 1} < a_j if the jjth letter in the string is U, and aj−1>aja_{j - 1} > a_j if the jjth letter in the string is D.

输入格式

The first line contains NN. The second line contains p1,p2,…,pNp_1,p_2,\ldots,p_N. The last line contains the string.

输出格式

Write out maximum possible value of KK.

数据范围

Test cases 3-4 satisfy N≤500N\le 500. Test cases 5-8 satisfy N≤5000N\le 5000. In test cases 9-12, the string consists of Us followed by Ds. Test cases 13-22 satisfy no additional constraints. Problem credits: Danny Mittal

样例

样例 1

5
1 5 3 4 2
UDUD
4
We 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.

样例 2

5
1 5 3 4 2
UUDD
3
We can choose $[a_0,a_1,a_2,a_3]=[p_1,p_3,p_4,p_5]$.