#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 cows (), conveniently numbered as usual, have ordered themselves according to a permutation of . You are also given a string of length consisting of the letters U and D. Please find the maximum such that there exists a subsequence of such that for all , if the th letter in the string is U, and if the th letter in the string is D.
输入格式
The first line contains . The second line contains . The last line contains the string.
输出格式
Write out maximum possible value of .
数据范围
Test cases 3-4 satisfy . Test cases 5-8 satisfy . 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]$.