Dãy Tăng Giảm

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John có $N$ con bò ( $2 \leq N \leq 3 \times 10^{5}$ ), được đánh số từ $1$ đến $N$ , xếp thành một hoán vị $p_{1}, p_{2}, \dots, p_{N}$ của các số từ $1$ đến $N$ .

Cho một xâu độ dài $N - 1$ chỉ gồm các ký tự U (tăng) và D (giảm). Hãy tìm giá trị $K$ lớn nhất ( $K \leq N - 1$ ) sao cho tồn tại một dãy con $a_{0}, a_{1}, \dots, a_{K}$ của $p$ (tức là chọn $K + 1$ phần tử theo đúng thứ tự trong $p$ ) thỏa mãn:

Với mỗi $j$ từ $1$ đến $K$ : nếu ký tự thứ $j$ của xâu là U thì $a_{j - 1} < a_{j}$ , nếu là D thì $a_{j - 1} > a_{j}$ .

Dữ liệu vào

Dòng 1: Số nguyên $N$ .
Dòng 2: $N$ số nguyên phân biệt $p_{1}, p_{2}, \dots, p_{N}$ — một hoán vị của $1 \dots N$ .
Dòng 3: Xâu độ dài $N - 1$ gồm các ký tự U và D.

Dữ liệu ra

Một số nguyên duy nhất — giá trị $K$ lớn nhất tìm được.

Ràng buộc

$2 \leq N \leq 3 \times 10^{5}$
$p$ là hoán vị của $1 \dots N$
Xâu có độ dài $N - 1$ và chỉ chứa U, D

Subtask:

Subtask 1 (9%): $N \leq 500$
Subtask 2 (18%): $N \leq 5000$
Subtask 3 (18%): Xâu gồm các ký tự U rồi đến các ký tự D (có thể không có phần nào)
Subtask 4 (55%): Không có ràng buộc thêm

Ví dụ

Input	Output	Giải thích
5 1 5 3 4 2 UDUD	4	Cả hoán vị $[1, 5, 3, 4, 2]$ thỏa mãn mẫu UDUD: $1 < 5 > 3 < 4 > 2$ .
5 1 5 3 4 2 UUDD	3	Dãy con $[1, 3, 4, 2]$ (chọn phần tử vị trí 1, 3, 4, 5) thỏa mãn UUDD: $1 < 3 < 4 > 2$ , cho $K = 3$ .

Ghi chú

Trong ví dụ 2, xâu UUDD có độ dài 4 nhưng không thể đạt $K = 4$ (sẽ cần dãy con độ dài 5 thỏa mãn UUDD, nhưng không tồn tại dãy con như vậy trong $p$ ).

Bình luận

Không có bình luận tại thời điểm này.