Cây cảnh
Đề bài
Tèo có một hàng cây gồm $N$ cây cảnh được đánh số từ 1 đến $N$ từ đầu hàng đến cuối hàng. Lúc mới trồng, tất cả các cây cảnh có chiều cao bằng nhau. Một thời gian sau, do cây phát triển không đồng đều nên trong hàng có cây cao cây thấp. Để làm tăng vẻ đẹp của hàng cây, Tèo quyết định loại bỏ một số cây để hàng cây thỏa mãn một trong 2 điều kiện: hoặc là chiều cao của các cây nhìn từ đầu hàng phải tăng dần; hoặc là chiều cao của các cây nhìn từ đầu hàng phải giảm dần (cây đứng sau phải thấp hơn cây đứng trước).
Yêu cầu: hãy tính xem phải loại bỏ những cây cảnh trong hàng như thế nào để số cây bị loại bỏ là ít nhất.
Dữ liệu vào: từ tệp văn bản TREE.INP
- Dòng 1: số nguyên dương $N$ $(N \le 10^5)$ là số cây cảnh có trong dãy.
- Dòng 2: ghi $N$ số nguyên $a_1, a_2, \ldots, a_N$ $(1 \le a_i \le 10^9)$ là chiều cao của các cây.
Kết quả: ghi ra tệp văn bản TREE.OUT là số nguyên duy nhất là số cây cảnh bị phá bỏ thỏa mãn yêu cầu của đề bài.
5
1 4 2 3 61cin/cout), đề bài có ghi tên file TREE.INP/TREE.OUT thì các bạn cứ kệ nó nhé.Giải thích ví dụ: hàng cây cao 1 4 2 3 6. Bỏ đi cây thứ 2 (cao 4) thì còn 1 2 3 6 tăng dần – chỉ phải bỏ 1 cây. Không thể bỏ 0 cây vì hàng ban đầu vừa có đoạn đi lên ($1 \to 4$) vừa có đoạn đi xuống ($4 \to 2$).
Lời mở đầu
Bỏ ít cây nhất cũng chính là giữ lại nhiều cây nhất. Các cây giữ lại vẫn đứng theo thứ tự cũ, tức là chúng tạo thành một dãy con của dãy chiều cao. Vậy bài toán quy về bài kinh điển của chương Quy hoạch động: dãy con tăng dài nhất (và giảm dài nhất). Mình sẽ đi từ cách vét cạn mọi cách giữ cây, sang QHĐ $O(N^2)$ quen thuộc, rồi tối ưu bằng chặt nhị phân để qua được $N = 10^5$.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | $N$ | Chiều cao $a_i$ | Có cây cao bằng nhau | Giữ lại nhiều nhất | Đáp án lớn nhất |
|---|---|---|---|---|---|
| 1–8 | 9 – 23 | 8 – 972.681.604 | 3/8 | 8 | 16 |
| 9–16 | 1.031 – 2.000 | 101 – 999.948.157 | 4/8 | 86 | 1.917 |
| 17–20 | 65.583 – 100.000 | 100 – 999.999.564 | 4/4 | 619 | 99.383 |
Đề không ghi subtask nhưng bộ test chia rất rõ thành 3 mức theo $N$, mình tự đặt tên là các mức dưới đây. Để ý: có nhiều test có các cây cao bằng nhau (các test 9–12, 17–18 có $a_i \le 50000$ nên trùng rất nhiều) – vì đề yêu cầu tăng dần / giảm dần thực sự (cây sau phải thấp hơn hẳn cây trước) nên 2 cây bằng nhau không được đứng cạnh nhau trong hàng giữ lại. Đây là chỗ hay sai nhất của bài.
| Mức | Điều kiện | Test | Cách 1 vét cạn bitmask | Cách 2 QHĐ $O(N^2)$ | Cách 3 QHĐ + chặt nhị phân |
|---|---|---|---|---|---|
| 1 | $N \le 23$ | 1–8 | qua | qua | qua |
| 2 | $N \le 2000$ | 9–16 | không chạy được | qua | qua |
| 3 | $N \le 10^5$ | 17–20 | không chạy được | quá thời gian | qua |
Ý tưởngGiữ lại nhiều cây nhất = dãy con tăng (giảm) dài nhất
Gọi $L_{tăng}$ là độ dài dãy con tăng ngặt dài nhất, $L_{giảm}$ là độ dài dãy con giảm ngặt dài nhất của dãy $a$. Tèo được chọn một trong hai kiểu nên số cây giữ lại nhiều nhất là $\max(L_{tăng}, L_{giảm})$ và
Để tính $L_{tăng}$ bằng quy hoạch động, ta đặt trạng thái theo cây cuối cùng được giữ lại:
- $f[i]$ = độ dài dãy con tăng dài nhất kết thúc tại cây $i$. Ta có $f[i] = 1 + \max\{ f[j] : j < i,\ a_j < a_i \}$ (nếu không có $j$ nào thì $f[i] = 1$ – chỉ giữ mình cây $i$).
- $g[i]$ = độ dài dãy con giảm dài nhất kết thúc tại cây $i$: $g[i] = 1 + \max\{ g[j] : j < i,\ a_j > a_i \}$.
- Kết quả: $\max(L_{tăng}, L_{giảm})$ $= \max_i \max(f[i], g[i])$.
Vì sao đúng? Dãy tăng kết thúc tại $i$ thì cây đứng ngay trước $i$ trong dãy đó là một cây $j < i$ thấp hơn hẳn $a_i$; phần trước đó là một dãy tăng kết thúc tại $j$, dài nhất là $f[j]$. Thử mọi $j$ rồi lấy cái tốt nhất. Chú ý dấu nhỏ hơn ngặt $a_j < a_i$: hai cây cao bằng nhau không được đứng liền nhau.
Em nhập chiều cao các cây rồi bấm Tiếp để xem bảng $f$, $g$ được điền dần (ô vàng là ô đang tính, ô xanh dương là các ô $j$ thỏa điều kiện mà nó được phép nối vào):
Cách 1Vét cạn mọi cách giữ cây (qua mức 1)
Cách "trâu" nhất: thử mọi tập cây được giữ lại. Mỗi số mask từ $1$ đến $2^N - 1$ ứng với một cách giữ: bit thứ $i$ bằng 1 nghĩa là giữ cây $i$. Với mỗi mask, đi qua các cây được giữ theo thứ tự và kiểm tra hàng đó có tăng ngặt hoặc giảm ngặt không.
if(truoc != -1) gộp luôn 2 phép so sánh bên trong cho mỗi cây được giữ.__builtin_popcount(mask)đếm số bit 1 = số cây giữ lại. Nếu con số này không vượt kỷ lụcbestthì khỏi kiểm tra – một mẹo cắt bớt nhỏ.- Biến
truocnhớ chỉ số cây giữ lại ngay trước cây $i$. Chỉ cần một cặp liền nhau "không tăng" làtang = false, "không giảm" làgiam = false.
Kết quả chạy thật: đúng 8/20 test (toàn bộ mức 1, chậm nhất 0,68 giây ở test $N = 23$). Từ test 9 trở đi $N \ge 1031$: mảng a[25] không đủ chỗ nên chương trình bị lỗi chạy – mà dù có khai báo mảng to thì $2^{1031}$ cách chọn cũng không bao giờ chạy xong. Bản Python của cách này còn chậm hơn nhiều nên mình không viết.
Cách 2Quy hoạch động $O(N^2)$ (qua mức 1, 2)
Cài đặt đúng công thức ở phần ý tưởng: với mỗi cây $i$, duyệt mọi cây $j$ đứng trước nó để tính cả $f[i]$ lẫn $g[i]$ trong cùng một vòng lặp.
f[i] = 1; g[i] = 1;– trường hợp tệ nhất là chỉ giữ một mình cây $i$.- Hai điều kiện
a[j] < a[i]vàa[j] > a[i]đều là so sánh ngặt; khia[j] == a[i]thì cây $j$ không được nối vào cả dãy tăng lẫn dãy giảm. bestlấy max của mọi $f[i]$, $g[i]$ – dãy dài nhất có thể kết thúc ở bất kỳ cây nào chứ không nhất thiết ở cây $N$.
Kết quả chạy thật: đúng 16/20 test, các test mức 1, 2 chạy dưới 0,01 giây. 4 test cuối có $N$ tới $10^5$: $\frac{N^2}{2} = 5 \cdot 10^9$ phép so sánh, chạy hơn 3,8 giây → quá thời gian. Bản Python cũng được 16/20.
Cách 3QHĐ + chặt nhị phân $O(N \log N)$ (full điểm)
Cách 2 chậm vì với mỗi $i$ phải dò lại toàn bộ các $j$ phía trước. Ta đổi cách lưu trạng thái:
Mảng $d$ luôn tăng ngặt (dãy dài hơn thì đuôi phải cao hơn), nên khi xét cây mới cao $x$ ta dùng lower_bound tìm vị trí đầu tiên có $d[k] \ge x$:
- Không có (mọi $d[k] < x$): $x$ nối được vào dãy dài nhất →
d.push_back(x), độ dài tăng thêm 1. - Có: thay $d[k] = x$ – có dãy độ dài $k + 1$ kết thúc bằng $x$ thấp hơn đuôi cũ.
Cuối cùng d.size() chính là $L_{tăng}$. Dùng lower_bound (tìm $\ge x$) chứ không phải upper_bound để hai cây bằng nhau thay thế nhau thay vì nối dài – đúng với yêu cầu tăng ngặt. Còn $L_{giảm}$? Dãy giảm ngặt của $a$ chính là dãy tăng ngặt của $-a$, nên chỉ cần gọi lại hàm với dãy $b_i = -a_i$.
Em thử nhập một dãy rồi bấm Tiếp để xem mảng $d$ thay đổi:
- Hàm
lisnhận vector theo tham chiếuconst &để không phải sao chép $10^5$ phần tử. *it = xghi đè đúng ô màlower_boundtrả về; mảng $d$ vẫn tăng ngặt sau khi ghi.- Lưu ý: $d$ không phải là một dãy con thật của $a$ (thứ tự các phần tử có thể bị xáo), nhưng độ dài của nó luôn đúng bằng độ dài dãy con tăng dài nhất.
Kết quả chạy thật: đúng 20/20 test, chậm nhất 0,02 giây. Bản Python (dùng bisect_left) cũng 20/20, chậm nhất 0,11 giây.
Nhận xét
Đăng nhận xét