| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P153SUME - ROUND 3E - Sắp xếp đồ thị |
Để sắp xếp 1 hoán vị từ 1 đến n, chúng ta có thể sử dụng thuật toán Bubble Sort. Bài toán quá nhàm chán nên AP đã phát triển nó thành 1 bài toán trên đồ thị. Với 1 hoán vị từ 1 đến n gồm n phần tử a[1], a[2], a[3], … a[n] cho trước, cùng 1 đồ thị ban đầu gồm n đỉnh, 0 cạnh, ta xây dựng đồ thị theo đoạn mã giả sau:
procedure bubbleSortGraph()
Tạo đồ thị n đỉnh, 0 cạnh
do
isSwapped = false
for i = 1 to n - 1 do:
if a[i] > a[i + 1] then
thêm 1 cạnh vào giữa a[i] và a[i+1]
swap( a[i], a[i + 1] )
isSwapped = true
end if
end for
while (swapped)
end procedure
Một tập hợp các đỉnh gọi là độc lập nếu trong tập hợp đó không tồn tại bất kỳ 2 đỉnh nào kề nhau. Hãy tìm kích cỡ của tập hợp lớn nhất có thể tìm thấy từ hoán vị đã cho.
Input
Dòng đầu tiên là số tự nhiên n (2 ≤ n ≤ 105).
Dòng tiếp theo gồm n số tự nhiên đôi một phân biệt a[1], a[2], …, a[n] (1≤ a[i] ≤ n).
Output
Kết quả của bài toán.
Example
Input:3
3 1 2 Output: 2
Giải thích: Đầu tiên chúng ta swap phần tử 1 và 3, tạo được cạnh (1,3) trên đồ thị. Cấu hình hoán vị mới là (1, 3, 2). Sau đó chúng ta swap phần tử 2 và 3, thêm cạnh (2, 3) vào đồ thị.
Tập hợp cạnh độc lập có kích cỡ lớn nhất là (1, 2).
| Được gửi lên bởi: | adm |
| Ngày: | 2015-07-16 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
