Chuyến du khảo (Đề tự luyện HSG Tin 9 – Bài 4)

Nguồn: Đề tự luyện HSG Tin học 9 – Bài 4 (đề tự soạn)Độ khó: KhóQuy hoạch độngQuay luiĐoạn con lớn nhất

Đề bài

Chuyến du khảo. Kênh Xà No có $N$ khúc liên tiếp, khúc $i$ có độ vui $a_i$ (có thể âm). Thầy Sơn chọn một đoạn khúc liên tiếp $[l, r]$ (ít nhất một khúc) cho ghe chạy qua, và được cho cả lớp ngủ ở tối đa $K$ khúc trong đoạn, không ngủ ở hai khúc liên tiếp. Khúc ngủ được tính độ vui $0$. Tìm tổng độ vui lớn nhất (tổng $a_i$ của các khúc thức).

Dữ liệu vào: dòng 1 là $N, K$ $(1 \le N \le 2\cdot 10^5,\ 0 \le K \le 10)$; dòng 2 là $a_1..a_N$ $(|a_i| \le 10^9)$.

Kết quả: tổng độ vui lớn nhất.

• Subtask 1 (20%): $N \le 15$.
• Subtask 2 (30%): $N \le 3000$, $K \ge 1$.
• Subtask 3 (50%): không ràng buộc thêm.

Input

9 2
9 7 -3 7 -8 -2 8 5 -1

Output

34

Giải thích

Chọn khúc $1..8$, ngủ ở khúc $3$ và khúc $5$: $9 + 7 + 0 + 7 + 0 - 2 + 8 + 5 = 34$.

Input

4 0
-5 -2 -7 -3

Output

-2

Giải thích

Không được ngủ, khúc nào cũng âm: chọn đoạn chỉ có khúc $2$.

Dành cho học viênNộp bài trên ClueOJ

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é. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Chuyến du khảo

Lời mở đầu

Nếu không có giấc ngủ nào ($K = 0$), đây là bài kinh điển "đoạn con có tổng lớn nhất". Giấc ngủ làm bài khó lên ở chỗ: ta phải chọn cùng lúc hai thứ — đoạn kênh và các khúc ngủ — và hai lựa chọn này ảnh hưởng lẫn nhau.

Hình 1. Dãy minh họa $a = 3, 4, -8, -1, 7, 6, 3, 0$ với $K = 2$ (khác ví dụ của đề): ngủ ở khúc 3 (khúc âm nhất) và đi luôn qua khúc 4 (−1) để tới đoạn 7, 6, 3 phía sau.

Vài "lối tắt" nghe rất hợp lý nhưng đều sai:

• Ngủ ở $K$ khúc âm nhất: trong dãy ở Hình 1, hai khúc âm nhất là $-8$ và $-1$ nằm liền nhau, không ngủ cả hai được.
• Tìm đoạn tốt nhất khi không ngủ, rồi mới cho ngủ ở các khúc âm trong đoạn: giấc ngủ có thể giúp "vượt" một khúc rất xấu để nối hai đoạn tốt lại với nhau, tức là làm thay đổi chính đoạn được chọn. Ví dụ với $a = 5, -9, 5$ và $K = 1$: không ngủ thì đoạn tốt nhất chỉ là $5$, nhưng ngủ ở khúc giữa thì được $5 + 0 + 5 = 10$.

Ví dụ 1 của đề được chọn sao cho cả hai lối tắt trên (và cả cách quên điều kiện "không ngủ hai khúc liền nhau") đều ra đúng $34$, nên qua được ví dụ chưa có nghĩa là code đúng. Bộ test có rất nhiều "bức tường" $-10^9$, có cả tường đôi (hai khúc $-10^9$ liền nhau, không thể ngủ vượt qua) để bắt các cách làm này. Ngoài ra còn hai chi tiết nhỏ: đáp án có thể âm (khi $K = 0$ và mọi $a_i < 0$) và có thể tới $2\cdot 10^{14}$ (cần long long).

Cách 1Quay lui · 20%Cách 2QHĐ với điểm bắt đầu cố định · 50%Cách 3QHĐ một lượt O(N·K) · 100%

Cách 1Quay lui – O(N · 2^N) · 20%

Thử mọi khúc bắt đầu $l$. Từ $l$, ta đi dần sang phải; ở mỗi khúc $i$ có hai lựa chọn: thức (cộng $a_i$) hoặc ngủ (cộng $0$, chỉ được khi còn lượt ngủ và khúc trước không ngủ). Mỗi khi đã đi qua ít nhất một khúc, ta có thể dừng chuyến tại đó, nên cập nhật kết quả ngay đầu hàm.

Hàm thu(i, daNgu, truocNgu, tong, rong) nhớ: đang xét khúc $i$, đã ngủ bao nhiêu lần, khúc trước có ngủ không, tổng độ vui hiện tại, và chuyến đi còn rỗng không. Với $N \le 15$, số trường hợp mỗi điểm bắt đầu không quá $2^{15}$, rất nhanh. Nhưng với $N = 3000$ thì số trường hợp bùng nổ.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, K;
vector<ll> a;
ll best = LLONG_MIN;
// chuyen di dang gom cac khuc l..i-1; quyet dinh tiep cho khuc i
void thu(int i, int daNgu, bool truocNgu, ll tong, bool rong) {
    if (!rong) best = max(best, tong);   // ket thuc chuyen o khuc i-1
    if (i == n) return;
    thu(i + 1, daNgu, false, tong + a[i], false);          // khuc i: thuc
    if (daNgu < K && !truocNgu)
        thu(i + 1, daNgu + 1, true, tong, false);          // khuc i: ngu
}
int main() {
    cin >> n >> K;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int l = 0; l < n; l++) thu(l, 0, false, 0, true);  // thu moi diem bat dau
    cout << best << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    a = [int(x) for x in data[2:2 + n]]
    best = None
    # quay lui bang ngan xep (tranh de quy): (i, da_ngu, truoc_ngu, tong, rong)
    for l in range(n):                       # thu moi diem bat dau
        st = [(l, 0, False, 0, True)]
        while st:
            i, dn, tn, tong, rong = st.pop()
            if not rong and (best is None or tong > best):
                best = tong                  # ket thuc chuyen o khuc i-1
            if i == n:
                continue
            st.append((i + 1, dn, False, tong + a[i], False))   # khuc i: thuc
            if dn < K and not tn:
                st.append((i + 1, dn + 1, True, tong, False))   # khuc i: ngu
    print(best)

main()

Không gian$O(N)$

Thời gian$O(N \cdot 2^N)$

Về bản Python

Bản Python dùng ngăn xếp tự quản lý thay cho đệ quy, để không bị giới hạn độ sâu đệ quy của Python.

Cách 2Quy hoạch động với điểm bắt đầu cố định – O(N²·K) · 50%

Quan sát lại phép quay lui: khi đang ở khúc $i$, để đi tiếp ta chỉ cần biết hai điều — đã ngủ bao nhiêu lần ($j$), và khúc vừa rồi có ngủ không. Mọi cách đi khác nhau mà có cùng $(i, j, \text{ngủ/thức})$ thì về sau đi y hệt nhau, nên chỉ cần giữ cách có tổng lớn nhất. Đó chính là trạng thái quy hoạch động:

• $thuc[j]$ = tổng lớn nhất của chuyến đi kết thúc ở khúc đang xét, đã ngủ $j$ lần, và thức ở khúc này;
• $ngu[j]$ = tương tự nhưng ngủ ở khúc này.

Khi sang khúc mới có độ vui $a$:

$$thuc'[j] = \max(thuc[j],\ ngu[j]) + a, \qquad ngu'[j] = thuc[j-1] \ (j \ge 1).$$

Thức thì khúc trước ngủ hay thức đều được; ngủ thì khúc trước bắt buộc thức, và tốn thêm một lượt ngủ. Trạng thái "không thể" ta gán $-\infty$ (trong code là $-10^{18}$).

Cố định điểm bắt đầu $l$: ở khúc $l$ thì $thuc[0] = a_l$, $ngu[1] = 0$ (nếu $K \ge 1$), còn lại $-\infty$. Sau đó đi $r = l+1, \dots, N$, mỗi bước cập nhật $2(K+1)$ giá trị, và lấy max của tất cả vào đáp án. Có $N$ điểm bắt đầu, mỗi cái chạy $O(N K)$, tổng $O(N^2 K)$: với $N = 3000, K = 10$ là khoảng $10^8$ phép đơn giản — vừa đủ nhanh.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG = -1000000000000000000LL;
int main() {
    int n, K;
    cin >> n >> K;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    ll ans = NEG;
    vector<ll> thuc(K + 1), ngu(K + 1), t2(K + 1), n2(K + 1);
    for (int l = 0; l < n; l++) {                 // co dinh khuc bat dau l
        fill(thuc.begin(), thuc.end(), NEG);
        fill(ngu.begin(), ngu.end(), NEG);
        for (int r = l; r < n; r++) {             // keo dai chuyen toi khuc r
            for (int j = 0; j <= K; j++) {
                ll truoc = max(thuc[j], ngu[j]);
                if (r == l) truoc = (j == 0) ? 0 : NEG;     // khuc dau tien
                t2[j] = (truoc == NEG) ? NEG : truoc + a[r];
                ll tr = (j >= 1) ? thuc[j - 1] : NEG;      // khuc truoc phai thuc
                if (r == l) tr = (j == 1) ? 0 : NEG;
                n2[j] = tr;
                ans = max(ans, max(t2[j], n2[j]));
            }
            swap(thuc, t2);
            swap(ngu, n2);
        }
    }
    cout << ans << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    a = [int(x) for x in data[2:2 + n]]
    NEG = -10 ** 18
    ans = NEG
    for l in range(n):                           # co dinh khuc bat dau l
        thuc = [NEG] * (K + 1)
        ngu = [NEG] * (K + 1)
        thuc[0] = a[l]                           # khuc dau tien: thuc
        if K >= 1:
            ngu[1] = 0                           # hoac ngu
        ans = max(ans, max(thuc), max(ngu))
        for r in range(l + 1, n):                # keo dai chuyen toi khuc r
            x = a[r]
            t2 = [max(thuc[j], ngu[j]) + x for j in range(K + 1)]
            n2 = [NEG] + thuc[:K]                # khuc truoc phai thuc
            m = max(max(t2), max(n2))
            if m > ans:
                ans = m
            thuc = t2
            ngu = n2
    print(ans)

main()

Không gian$O(N + K)$

Thời gian$O(N^2 K)$

Cách 3Quy hoạch động một lượt – O(N·K) · 100%

Ở Cách 2, các điểm bắt đầu khác nhau chỉ khác nhau ở khúc đầu tiên. Thay vì chạy lại từ đầu cho mỗi $l$, ta gộp tất cả vào một lượt duy nhất: tại mỗi khúc $i$, ngoài việc nối tiếp chuyến cũ, ta cho phép bắt đầu chuyến mới ngay tại $i$. Bắt đầu chuyến mới giống như nối tiếp một "chuyến rỗng" có tổng $0$, đã ngủ $0$ lần:

$$thuc'[0] = \max(thuc[0],\ ngu[0],\ \mathbf{0}) + a,\qquad thuc'[j] = \max(thuc[j],\ ngu[j]) + a\ \ (j \ge 1),$$ $$ngu'[1] = \max(thuc[0],\ \mathbf{0}),\qquad ngu'[j] = thuc[j-1]\ \ (j \ge 2).$$

Hai số $\mathbf{0}$ in đậm chính là "bắt đầu chuyến mới": bắt đầu bằng một khúc thức (với $j = 0$), hoặc bắt đầu bằng một giấc ngủ (với $j = 1$). Với $K = 0$, công thức thứ nhất chính là thuật toán Kadane quen thuộc! Đáp án là giá trị lớn nhất trong mọi $thuc[j], ngu[j]$ tại mọi khúc (với mọi $j \le K$, vì ngủ ít hơn $K$ lần cũng được).

Chạy tay dãy ở Hình 1 ($K = 2$)

khúc i	ai	thuc[0]	thuc[1]	thuc[2]	ngu[1]	ngu[2]	max đến giờ
1	3	3	−∞	−∞	0	−∞	3
2	4	7	4	−∞	3	−∞	7
3	−8	−1	−4	−∞	7	4	7
4	−1	−1	6	3	0	−4	7
5	7	7	13	10	0	6	13
6	6	13	19	16	7	13	19
7	3	16	22	19	13	19	22
8	0	16	22	19	16	22	22

Chú ý hàng khúc $4$: $ngu[2] = thuc[1]$ của khúc $3$ $= -4$ — muốn ngủ ở khúc $4$ khi đã ngủ ở khúc $3$ là không được, nên ngủ lần thứ hai ở khúc $4$ chỉ có thể nối từ chuyến "thức ở khúc 3", rất tệ. Còn $thuc[1] = \max(-4, 7) + (-1) = 6$ ở khúc $4$ là "đã ngủ ở khúc 3, thức qua khúc 4". Cuối cùng đáp án là $22$ (ở khúc $7$, $thuc[1]$).

Mô phỏng sau đây cho các bạn tự nhập dãy và xem bảng QHĐ được điền từng khúc.

Dãy a K

Ví dụ nhanh:

Ba chi tiết dễ mất điểm

• Khởi tạo ans: phải là $-\infty$, không phải $0$. Với $K = 0$ và toàn số âm (ví dụ 2), đáp án là số âm.
• long long: tổng có thể tới $2\cdot 10^5 \cdot 10^9 = 2\cdot 10^{14}$.
• Giá trị $-\infty$: chọn $-10^{18}$. Trạng thái "không thể" có thể bị cộng thêm $a_i$ nhiều lần, nhưng tổng cộng chỉ lệch tối đa $2\cdot 10^{14}$, vẫn rất âm và không tràn số. Đừng chọn LLONG_MIN vì cộng thêm số âm là tràn ngay!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG = -1000000000000000000LL;    // "khong the" (-10^18)
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, K;
    cin >> n >> K;
    // thuc[j]: chuyen di ket thuc o khuc dang xet, da ngu j lan, khuc nay THUC
    // ngu[j] : ... khuc nay NGU
    vector<ll> thuc(K + 1, NEG), ngu(K + 1, NEG), t2(K + 1), n2(K + 1);
    ll ans = NEG;
    for (int i = 0; i < n; i++) {
        ll a;
        cin >> a;
        for (int j = 0; j <= K; j++) {
            ll truoc = max(thuc[j], ngu[j]);       // noi tiep chuyen cu
            if (j == 0) truoc = max(truoc, 0LL);   // hoac bat dau chuyen moi tai day
            t2[j] = truoc + a;
            if (j == 0) n2[j] = NEG;
            else {
                ll tr = thuc[j - 1];               // khuc truoc phai THUC
                if (j == 1) tr = max(tr, 0LL);     // hoac bat dau chuyen moi bang giac ngu
                n2[j] = tr;                        // ngu: khuc nay duoc 0 diem
            }
            ans = max(ans, max(t2[j], n2[j]));
        }
        swap(thuc, t2);
        swap(ngu, n2);
    }
    cout << ans << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    a = data[2:2 + n]
    NEG = -10 ** 18                     # "khong the"
    # thuc[j]: chuyen di ket thuc o khuc dang xet, da ngu j lan, khuc nay THUC
    # ngu[j] : ... khuc nay NGU
    thuc = [NEG] * (K + 1)
    ngu = [NEG] * (K + 1)
    ans = NEG
    rk = range(1, K + 1)
    for i in range(n):
        x = int(a[i])
        t2 = [0] * (K + 1)
        n2 = [NEG] * (K + 1)
        # j = 0: noi tiep chuyen cu, hoac bat dau chuyen moi tai day
        t2[0] = max(thuc[0], ngu[0], 0) + x
        for j in rk:
            t2[j] = max(thuc[j], ngu[j]) + x
            if j == 1:
                n2[1] = max(thuc[0], 0)     # bat dau chuyen moi bang giac ngu
            else:
                n2[j] = thuc[j - 1]         # khuc truoc phai THUC
        m = max(max(t2), max(n2))
        if m > ans:
            ans = m
        thuc = t2
        ngu = n2
    print(ans)

main()

Không gian$O(K)$

Thời gian$O(N K)$

C++▶ Chạy tay từng dòng codeMỗi khúc cập nhật thuc[j], ngu[j] (j = 0..K) từ khúc trước, có thêm lựa chọn "bắt đầu chuyến mới".

Dữ liệu vào (stdin) – sửa thoải mái9 2 9 7 -3 7 -8 -2 8 5 -1

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3typedef long long ll;

4const ll NEG = -1000000000000000000LL; // "khong the" (-10^18)

5int main() {

6 ios::sync_with_stdio(false);

7 cin.tie(nullptr);

8 int n, K;

9 cin >> n >> K;

10 // thuc[j]: chuyen di ket thuc o khuc dang xet, da ngu j lan, khuc nay THUC

11 // ngu[j] : ... khuc nay NGU

12 vector<ll> thuc(K + 1, NEG), ngu(K + 1, NEG), t2(K + 1), n2(K + 1);

13 ll ans = NEG;

14 for (int i = 0; i < n; i++) {

15 ll a;

16 cin >> a;

17 for (int j = 0; j <= K; j++) {

18 ll truoc = max(thuc[j], ngu[j]); // noi tiep chuyen cu

19 if (j == 0) truoc = max(truoc, 0LL); // hoac bat dau chuyen moi tai day

20 t2[j] = truoc + a;

21 if (j == 0) n2[j] = NEG;

22 else {

23 ll tr = thuc[j - 1]; // khuc truoc phai THUC

24 if (j == 1) tr = max(tr, 0LL); // hoac bat dau chuyen moi bang giac ngu

25 n2[j] = tr; // ngu: khuc nay duoc 0 diem

26 }

27 ans = max(ans, max(t2[j], n2[j]));

28 }

29 swap(thuc, t2);

30 swap(ngu, n2);

31 }

32 cout << ans << '\n';

33 return 0;

34}

ChậmVừaNhanhRất nhanh

Bộ test chấm "bắt" những lỗi nào?

Bộ test có 32 test: Subtask 1 có 10 test ($N \le 15$, gồm hai ví dụ, $N = 1$ với $K = 0$ và $K = 1$, toàn số âm), Subtask 2 có 10 test ($N \approx 3000$, $1 \le K \le 10$), Subtask 3 có 12 test ($N \approx 2\cdot 10^5$, $K$ từ $0$ đến $10$). Các test dùng nhiều kiểu dãy: ngẫu nhiên, nghiêng về số dương (tổng cỡ $5\cdot 10^{13}$), nhiều cặp số âm lớn đứng liền nhau, các cụm dương nhỏ ngăn bởi "tường" $-10^9$ đơn và đôi, toàn số âm với $K = 0$. Điểm tính theo từng test (thang 100%).

Cách làm	Sub 1 (10 test)	Sub 2 (10 test)	Sub 3 (12 test)	Điểm
Cách 1 – Quay lui	Đúng 10/10	TLE 0/10	0/12 (TLE/tràn ngăn xếp)	20
Cách 2 – QHĐ với điểm bắt đầu cố định, $O(N^2K)$	Đúng 10/10	Đúng 10/10	TLE 0/12	50
Cách 3 – QHĐ một lượt, $O(NK)$ (chuẩn)	Đúng 10/10	Đúng 10/10	Đúng 12/12	100
Sai: khởi tạo ans = 0	WA 8/10	Đúng 10/10	WA 11/12	91,8
Sai: dùng int thay cho long long	WA 8/10	WA 2/10	WA 3/12	34,5
Sai: quên điều kiện "không ngủ hai khúc liên tiếp"	WA 7/10	WA 6/10	WA 8/12	65,3
Sai: Kadane rồi ngủ ở các khúc âm nhất trong đoạn	WA 7/10	WA 4/10	WA 6/12	51

Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test Subtask 1, quá thời gian (hơn 3 giây) ở cả 10 test Subtask 2, và ở Subtask 3 thì chết vì đệ quy sâu $2\cdot 10^5$ tầng (nếu máy chấm cho ngăn xếp lớn thì cũng quá thời gian); Cách 2 đúng 20/20 test của hai subtask đầu và quá thời gian ở cả 12 test Subtask 3; Cách 3 đúng 32/32 test, test lâu nhất chạy khoảng 0,08 giây. Lời giải Python của Cách 3 cũng đúng 32/32 test, chạy tối đa khoảng 1,5 giây với CPython. Lỗi khởi tạo ans = 0 chỉ bị bắt ở 3 test có $K = 0$ và toàn số âm — một lỗi nhỏ nhưng mất gần 10% số điểm.

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 😇