Dãy hình nón

Nguồn: CLUE OJ – Chương 22: Quy hoạch động Độ khó: Trung bình Quy hoạch động Dãy con tăng – giảm

Đề bài

Dãy số $b_1, b_2, \dots, b_m$ được gọi là hình nón nếu tồn tại $j$ sao cho $b_1 < b_2 < \dots < b_j > b_{j+1} > \dots > b_m$ $(1 < j < m)$. Theo định nghĩa ta thấy dãy số hình nón phải có ít nhất 3 phần tử.

Cho dãy số nguyên $a_1, a_2, \dots, a_n$. Dãy số $a_{i_1}, a_{i_2}, \dots, a_{i_k}$ được gọi là dãy con của dãy đã cho nếu $1 \le i_1 < i_2 < \dots < i_k$ $\le n$.

Yêu cầu: cho dãy số nguyên, các số ở hệ thập phân. Hãy xác định dãy con hình nón có tổng các số lớn nhất và đưa ra tổng này.

Dữ liệu: vào từ file văn bản BITONIC.INP gồm:

• Dòng đầu tiên chứa số nguyên $n$ $(3 \le n \le 1000)$,
• Dòng thứ 2 chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^5)$.

Kết quả: đưa ra file văn bản BITONIC.OUT một số nguyên – kết quả tìm được.

Ví dụ – input

4
2 1 3 1

Ví dụ – output

6

Lưu ý khi nộp bài

Đề gốc đọc/ghi file BITONIC.INP / BITONIC.OUT. Code bên dưới dùng if (fopen("BITONIC.INP", "r")) { freopen(...); }: có file thì đọc file, không có thì đọc bàn phím – nộp trên CLUE OJ hay Codeforces đều được. Bộ test chính thức đều có ít nhất một dãy con hình nón; nếu không có, code in ra 0.

Lời mở đầu

Bài này là "biến thể tổng" của bài dãy con tăng dài nhất (LIS). Một dãy hình nón gồm một đoạn tăng đi lên tới đỉnh rồi một đoạn giảm đi xuống. Nếu biết với mỗi vị trí $i$: "đoạn tăng tốt nhất kết thúc ở $i$" và "đoạn giảm tốt nhất bắt đầu ở $i$" thì ghép lại là xong. Mình đi từ cách vét cạn để hiểu bài, rồi tới QHĐ.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

Dành cho tất cả mọi ngườiNộp bài trên Codeforces

Bạ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 Codeforces

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test10 testÝ tưởngMảng L, RCách 1Quay lui 20%Cách 2QHĐ 100%

Bộ testBộ test chính thức có gì?

Test	$n$	Khoảng giá trị $a_i$	Số giá trị khác nhau	Đáp án
1	10	12.570–93.403	10	377.790
2	40	1.154–99.075	40	920.742
3	80	1.273–99.746	80	1.246.160
4	100	2.578–99.121	100	1.545.584
5	500	668–99.824	499	3.268.577
6	600	73–99.391	598	3.596.558
7	700	22–99.802	697	3.967.280
8	800	99–99.845	796	4.370.845
9	900	56–99.990	893	5.073.492
10	1000	59–99.845	995	4.718.236

Chỉ có 10 test, $n$ tăng dần từ 10 lên 1000, các số là ngẫu nhiên đến $10^5$. Đề không chia subtask, mình tạm chia 3 mức để so sánh các cách giải. Đáp án tới khoảng $5 \cdot 10^6$ vẫn vừa int, nhưng tổng lý thuyết tới $1000 \cdot 10^5 = 10^8$ – mình vẫn dùng long long cho chắc.

Mức	Điều kiện	Test	Cách 1 (quay lui)	Cách 2 (QHĐ $O(n^2)$)
1	$n \le 40$	1–2	qua	qua
2	$n \le 100$	3–4	quá thời gian	qua
3	$500 \le n \le 1000$	5–10	quá thời gian	qua

Ý tưởngHai mảng L và R, ghép tại đỉnh

Hai mảng quy hoạch động

• L[i] = tổng lớn nhất của một dãy con tăng chặt kết thúc tại $i$: $L[i] = a_i + \max\big(0,\ \max\{L[j] : j < i,\ a_j < a_i\}\big)$.
• R[i] = tổng lớn nhất của một dãy con giảm chặt bắt đầu tại $i$: $R[i] = a_i + \max\big(0,\ \max\{R[j] : j > i,\ a_j < a_i\}\big)$ – tính từ phải sang trái.
• Chọn $i$ làm đỉnh: tổng là $L[i] + R[i] - a_i$ (vì $a_i$ bị đếm 2 lần). Điều kiện $1 < j < m$ nghĩa là đỉnh phải có ít nhất 1 số bên trái và 1 số bên phải: $L[i] > a_i$ và $R[i] > a_i$ (đúng vì mọi $a_i \ge 1$).

Em nhập dãy rồi bấm Tiếp: lượt 1 điền L từ trái sang, lượt 2 điền R từ phải sang, lượt 3 thử từng đỉnh:

vị trí đang tínhcác số nhỏ hơn được xétdãy con tốt nhất

Dãy a

Ví dụ nhanh:

Cách 1Quay lui sinh mọi dãy con hình nón (mức 1)

Duyệt từng phần tử, chọn hoặc không chọn – nhưng chỉ đi theo các nhánh vẫn còn có thể thành hình nón: khi đang đi lên thì được chọn số lớn hơn số cuối (tiếp tục lên), hoặc số nhỏ hơn nếu đã có ít nhất 2 số (bắt đầu đi xuống, số cuối chính là đỉnh); khi đã đi xuống thì chỉ được chọn số nhỏ hơn.

C++▶ Chạy tay từng dòng codeCách 1: quay lui chỉ đi theo các nhánh còn có thể thành hình nón.

Dữ liệu vào (stdin) – sửa thoải mái4 2 1 3 1

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Khung bên phải là ngăn xếp lời gọi, mỗi tầng ghi số cuối, độ dài, hướng đang đi và tổng.

Không gian$O(n)$ (độ sâu đệ quy)

Thời gian$O(2^n)$ trường hợp xấu

Kết quả chạy thật: đúng 2/10 test (test 1 có $n = 10$, test 2 có $n = 40$ chạy 0,014 giây vì dãy ngẫu nhiên cắt bớt nhiều nhánh). Từ test 3 ($n = 80$) trở đi số dãy con hình nón bùng nổ → quá thời gian.

Cách 2Quy hoạch động $O(n^2)$ (full điểm)

C++▶ Chạy tay từng dòng codeCách 2: mảng L (tăng, kết thúc tại i) và R (giảm, bắt đầu tại i), ghép tại đỉnh.

Dữ liệu vào (stdin) – sửa thoải mái4 2 1 3 1

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Con trỏ i là vị trí đang tính, j là vị trí đang so sánh.

1. Khởi tạo L[i] = a[i]: dãy chỉ có một mình $a_i$. Sau đó thử nối vào sau mọi $j < i$ có $a_j < a_i$.
2. Vòng tính R đi ngược từ $n$ về $1$ vì R[i] cần các R[j] với $j > i$ đã có trước.
3. Điều kiện L[i] > a[i] && R[i] > a[i] loại các "đỉnh" nằm ở mép (chỉ có đoạn tăng hoặc chỉ có đoạn giảm) – đó là chỗ hay sai nhất của bài.

Không gian$O(n)$

Thời gian$O(n^2)$

Kết quả chạy thật: bản C++ đúng 10/10 test, chậm nhất 0,005 giây; bản Python đúng 10/10 test, chậm nhất 0,074 giây. Với $n \le 1000$ thì $n^2 = 10^6$ phép tính là quá thoải mái.

Mở rộng: nếu $n$ lên tới $10^5$ thì thay vòng for j bằng cây Fenwick (BIT) lưu max theo giá trị $a_j$, độ phức tạp còn $O(n \log n)$ – cùng kỹ thuật với LIS $O(n \log n)$.

Ghi chú của mình: trên 10 test chính thức (1 giây): cách 1 quay lui 2/10 (quá thời gian từ $n = 80$); cách 2 QHĐ 10/10 (C++ 0,005 s, Python 10/10). Nhớ 2 chi tiết: dãy phải tăng/giảm chặt (dùng dấu <), và đỉnh không được nằm ở 2 đầu.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇