Up Down Subsequence

题目描述

农夫约翰的 $N$ 头奶牛（$2 \leq N \leq 3\cdot 10^5$），像往常一样方便地编号为 $1\ldots N$，它们按照一个排列 $p_1,p_2,\ldots,p_N$（为 $1\ldots N$ 的一个排列）排成了一列。 你还会得到一个长度为 $N-1$ 的字符串，只由字母 U 和 D 组成。请你找到最大的 $K\le N-1$，使得存在 $p$ 的一个子序列 $a_0,a_1,\ldots,a_{K}$，满足对所有 $1\le j\le K$：若字符串的第 $j$ 个字符为 U，则 $a_{j - 1} < a_j$；若字符串的第 $j$ 个字符为 D，则 $a_{j - 1} > a_j$。

输入格式

第一行包含 $N$。 第二行包含 $p_1,p_2,\ldots,p_N$。 最后一行包含该字符串。

输出格式

输出最大的可能值 $K$。

5
1 5 3 4 2
UDUD

4

5
1 5 3 4 2
UUDD

3

提示

我们可以选择 $[a_0,a_1,a_2,a_3,a_4]=[p_1,p_2,p_3,p_4,p_5]$；整个排列都与该字符串一致。 我们可以选择 $[a_0,a_1,a_2,a_3]=[p_1,p_3,p_4,p_5]$。 评分： 测试点 3-4 满足 $N\le 500$。 测试点 5-8 满足 $N\le 5000$。 在测试点 9-12 中，字符串由若干个 U 后接若干个 D 组成。 测试点 13-22 无额外限制。 题目署名：Danny Mittal

标签: USACO|2022|Platinum

来源

USACO|2022|Platinum