trang chủ / đề bài / icpc22_mn_g

Dãy con dài nhất

Đề bài

Mô tả

Cho một hoán vị gồm n số từ 1 đến n là p1,p2,…,pn và m cặp chỉ số (u,v) với 1≤u,v≤n. Bạn có thể thực hiện một loạt các bước dựa trên các cặp này. Ở mỗi bước, bạn chọn một cặp và đổi chỗ hai số ở vị trí u và v trong hoán vị p. Mỗi cặp có thể được dùng bao nhiêu lần tùy ý.

Một dãy con tăng độ dài k của p là

pj1<pj2<⋯<pjk với j1<j2<⋯<jk

Gọi maxk là độ dài dãy con tăng dài nhất của p.

Nhiệm vụ của bạn là thực hiện các bước đổi chỗ để thu được hoán vị p có maxk lớn nhất.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và m.
  • Dòng thứ hai chứa hoán vị p1,p2,…,pn.
  • Mỗi dòng trong m dòng tiếp theo chứa hai số nguyên u, v.

Dữ liệu ra

In ra một số nguyên duy nhất là giá trị lớn nhất của maxk.

Ràng buộc

  • 1≤n≤104
  • 0≤m≤min(105,n(n−1)2)
  • 1≤u,v≤n

Ví dụ

Input Output Giải thích
6 2
5 2 4 6 3 1
5 6
1 5
4 Thực hiện hai bước (5,6) và (1,5) để được hoán vị (1,2,4,6,5,3), có dãy con tăng 1,2,4,6 độ dài 4.
7 3
6 2 3 1 5 7 4
1 3
2 5
6 7
4 Ví dụ bổ sung (không có trong đề gốc). Có thể đạt hoán vị (3,5,6,1,2,4,7) với dãy con tăng 3,5,6,7. Lưu ý rằng xếp tăng dần các giá trị trong mỗi nhóm vị trí đổi chỗ được cho nhau, tức (3,2,6,1,5,4,7), chỉ cho độ dài 3.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0