Không Được Cắt Nhau II

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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

Nông dân John có một trang trại với hai dãy cánh đồng nằm song song hai bên một con đường lớn. Mỗi bên có đúng $N$ cánh đồng, được đánh số vị trí từ $1$ đến $N$ từ trái sang phải. Mỗi cánh đồng nuôi một giống bò khác nhau, được mã hiệu bởi một số nguyên từ $1$ đến $N$ . Mỗi mã hiệu xuất hiện đúng một lần ở mỗi bên.

Nông dân John muốn xây dựng các lối đi ngang qua con đường để kết nối các cánh đồng ở hai phía. Một lối đi có thể được xây dựng nếu hai cánh đồng mà nó nối có mã hiệu giống bò thân thiện với nhau, tức là hai mã hiệu chênh lệch nhau không quá $4$ .

Hai lối đi được gọi là giao nhau nếu một lối đi nối cánh đồng thứ $i$ bên A với cánh đồng thứ $j$ bên B, và lối đi còn lại nối cánh đồng thứ $i^{'}$ bên A với cánh đồng thứ $j^{'}$ bên B, với $(i - i^{'}) (j - j^{'}) < 0$ (tức là một lối đi "vượt qua" lối đi kia).

Hơn nữa, mỗi cánh đồng chỉ được phép kết nối với tối đa một lối đi.

Hãy tìm số lượng lối đi tối đa có thể xây dựng sao cho không có hai lối đi nào giao nhau.

Dữ liệu vào

Dòng đầu tiên: số nguyên $N$ ( $1 \leq N \leq 10^{5}$ ).
$N$ dòng tiếp theo: mã hiệu giống bò của các cánh đồng bên A, từ vị trí $1$ đến $N$ .
$N$ dòng tiếp theo: mã hiệu giống bò của các cánh đồng bên B, từ vị trí $1$ đến $N$ .

Dữ liệu ra

In ra một số nguyên duy nhất — số lượng lối đi tối đa không giao nhau.

Ràng buộc

$1 \leq N \leq 10^{5}$
Mỗi mã hiệu từ $1$ đến $N$ xuất hiện đúng một lần ở mỗi bên

Ví dụ

Input	Output	Giải thích
6 1 2 3 4 5 6 6 5 4 3 2 1	5	Bên A: [1,2,3,4,5,6], Bên B: [6,5,4,3,2,1]. Ta có thể xây 5 lối đi: A[1]↔B[5] (mã 1↔2, chênh 1), A[2]↔B[4] (mã 2↔3, chênh 1), A[3]↔B[3] (mã 3↔4, chênh 1), A[4]↔B[2] (mã 4↔5, chênh 1), A[5]↔B[1] (mã 5↔6, chênh 1). Các lối đi này không giao nhau và mỗi cánh đồng chỉ dùng một lần.

Ghi chú

Hai giống bò có mã hiệu $a$ và $b$ là thân thiện nếu $| a - b | \leq 4$ .

Trong ví dụ trên, cặp A[6]↔B[?] (mã 6) chỉ có thể ghép với mã từ $2$ đến $N$ ; mã $2$ ở B nằm ở vị trí $5$ (đã dùng), mã $3, 4, 5$ ở B cũng đã dùng, nên không thể thêm lối đi thứ 6 mà không gây giao nhau.

Bình luận

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