P6975: 上下子序列
传统题
1.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
【题目描述】
Farmer John
的 N
头奶牛（2≤N≤3×10
^5
），编号为1…N，排列成 1…N
的一个排列p1,p2,…,pN。另外给定一个长为 N−1
的字符串，由字母 U 和 D 组成。请求出最大的 K≤N−1，使得存在 p
的一个子序列 a0,a1,…,aK，满足对于所有 1≤j≤K
，当字符串中第 j
个字母是 U 时 aj−1<aj，当字符串中的第 jj
个字母是 D 时 aj−1>ajaj−1>aj
。
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含 N
。
第二行包含 p1,p2,…,pN
。
最后一行包含给定的字符串。
【
输出格式】
（输出至终端 /
标准输出）：
输出 K
的最大可能值。
【
输入样例】
：
5
1 5 3 4 2
UDUD
【
输出样例】
：
4
【样例说明】
我们可以选择 [a0,a1,a2,a3,a4]=[p1,p2,p3,p4,p5]
；整个排列与给定的字符串相一致。
【
输入样例】
：
5
1 5 3 4 2
UUDD
【
输出样例】
：
3
【样例说明】
我们可以选择[a0,a1,a2,a3]=[p1,p3,p4,p5]
。
【
测试点性质】
：
测试点 3-4
满足 N≤500。
测试点 5-8
满足 N≤5000。
测试点 9-12
中，字符串中的 U 均在 D 之前。
测试点 13-22
没有额外限制。