Công Chúa (DPPRINCESS)

Nguồn: VinhDinhCoder Độ khó: Dễ Quy hoạch động QHĐ tuyến tính

Đề bài

DPPRINCESS – Công chúa

Giới hạn thời gian: 1.0 giây. Giới hạn bộ nhớ: 128 megabyte.

Ngày xửa ngày xưa có một nàng công chúa dễ thương tên là Farida sống trong một lâu đài cùng với cha, mẹ và chú của mình. Trên đường đến lâu đài có nhiều quái vật. Mỗi người trong số họ có một số tiền vàng. Mặc dù chúng là quái vật nhưng chúng sẽ không làm bạn bị thương. Thay vào đó, chúng sẽ đưa cho bạn những đồng tiền vàng, nhưng quái vật $i$ chỉ đưa vàng cho bạn khi và chỉ khi bạn không lấy bất kỳ đồng xu nào từ quái vật $i - 1$.

Để kết hôn với công chúa Farida, bạn phải vượt qua tất cả các quái vật và thu thập càng nhiều tiền càng tốt. Dựa vào số lượng đồng xu vàng mà mỗi quái vật có, hãy tính số lượng tiền tối đa bạn có thể thu thập trên đường đến lâu đài.

Dữ liệu nhập:

Dòng đầu tiên chứa số nguyên $t$ là số lượng test $(1 \le t \le 10)$.
Mỗi trường hợp thử nghiệm bắt đầu bằng $N$ – số lượng quái vật $(0 \le N \le 10^4)$.
Dòng tiếp theo sẽ có $N$ số $x_1, x_2, \ldots, x_n$ $(0 \le x_i \le 10^9)$. Với $x_i$ là số đồng vàng quái vật thứ $i$ có. Quái vật được mô tả theo thứ tự họ gặp trên đường đến lâu đài.

Kết quả: In ra $t$ dòng, mỗi dòng là một đáp án cho một trường hợp thử nghiệm.

Ví dụ – input

Ví dụ – output

9
10

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Đây là một bài quy hoạch động "nhập môn" rất kinh điển, nhưng mình sẽ đi thêm một bước: từ code trực quan nhất, tối ưu dần cả về thời gian lẫn bộ nhớ để các bạn thấy được chỗ nào có thể "gọt" được nha.

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Nói gọn lại: ta có một dãy số, được chọn các số sao cho không có 2 số nào đứng liền kề nhau, hỏi tổng lớn nhất là bao nhiêu.

Test 1 có $N = 5$ quái vật với số vàng $1, 2, 3, 4, 5$. Lấy của quái vật $1, 3, 5$ (không có 2 con nào liền kề) được $1 + 3 + 5 = 9$. Các cách khác như lấy $2 + 4 = 6$, $2 + 5 = 7$, $1 + 4 = 5$… đều ít hơn, nên đáp án là 9.
Test 2 chỉ có $N = 1$ quái vật với $10$ đồng vàng, cứ thế lấy luôn, đáp án là 10.

QV 11QV 22QV 33QV 44QV 55⇒ 1 + 3 + 5 = 9

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

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

Cách 1QHĐ 2 mảng X, F · O(T·N)Cách 2Gộp đọc & xử lý, bỏ mảng X Cách 3Chỉ 3 biến · bộ nhớ O(1)

Cách 1Quy hoạch động 4 bước – O(T·N)

Bài này áp dụng phương pháp Quy Hoạch Động (Dynamic Programming) để giải quyết nhé các bạn. Cho bạn nào đã biết cơ bản qua về quy hoạch động rồi thì 4 bước giải một bài toán quy hoạch động như sau.

1Bài toán con: $F[i]$ là tổng tiền vàng lớn nhất khi xét qua $i$ quái vật đầu tiên.

2Bài toán cơ sở: $F[0] = 0$, $F[1] = X[1]$.

3Đáp án: $F[N]$.

4Truy hồi: $F[i] = \max(F[i-1],\ F[i-2] + X[i])$.

Bước 1: Xác định bài toán con

Gọi $F[i]$ là tổng số tiền vàng lớn nhất đã thu được khi xét qua $i$ quái vật, tức là tính từ quái vật đầu tiên (gọi là thứ 1) và xét đến hết quái vật thứ $i$.

Bước 2: Xác định bài toán cơ sở

$F[0] = 0$: nếu không có quái vật nào hết thì chẳng thu được đồng tiền vàng nào.
$F[1] = X[1]$: nếu chỉ có 1 quái vật duy nhất thì số vàng thu được chính là số vàng của quái vật đó (vàng không âm, lấy luôn cho khỏe).

Bước 3: Xác định đáp án bài toán

Quá rõ ràng đó chính là $F[N]$ – tổng số tiền vàng lớn nhất thu được sau khi xét qua cả $N$ quái vật, cũng là đáp án mà đề bài đang cần tìm.

Bước 4: Xác định công thức truy hồi

Ở bước 1 ta gọi $F[i]$ là tổng tiền vàng lớn nhất khi xét qua $i$ quái vật, thì $F[i-1]$ là tổng lớn nhất khi xét qua $i-1$ quái vật, tương tự $F[i-2]$ là khi xét qua $i-2$ quái vật. Nguyên tắc của quy hoạch động (cũng như đệ quy) là ta giả định những kết quả $F[i-1]$, $F[i-2]$ đều đã được tính chính xác rồi, và từ đó tính ra $F[i]$.

Đề nói quái vật $i$ chỉ đưa tiền vàng khi trước đó ta không lấy tiền của quái vật $i-1$. Vậy $F[i]$ có 2 tình huống:

1/ Không lấy tiền quái vật $i$

(ví dụ vì đã lấy tiền của quái vật $i-1$). Khi đó tổng lớn nhất khi xét đến quái vật $i$ chính là tổng lớn nhất khi xét đến quái vật $i-1$: $F[i] = F[i-1] + 0$.

2/ Lấy tiền quái vật $i$

thì bắt buộc không được lấy của quái vật $i-1$, tức là trước đó chỉ lấy tiền trong $i-2$ quái vật đầu: $F[i] = F[i-2] + X[i]$.

Khi $F[i]$ có 2 lựa chọn như vậy, để tổng tiền vàng lớn nhất thì ta lấy kết quả lớn nhất của 2 trường hợp:

Công thức truy hồi

$F[i] = \max\big(F[i-1],\ F[i-2] + X[i]\big)$ với $i \ge 2$, đáp án là $F[N]$.

2 chỗ dễ "văng lỗi"

Khi $i = 2$ thì $F[i-2]$ chính là $F[0]$, nên các bạn phải nhớ đặt bài toán cơ sở $F[0] = 0$ nhé, không có là sai đấy.
Đề cho $N \ge 0$, tức là có thể có test $N = 0$. Lúc đó làm gì có $X[1]$? Nên bước khởi tạo $F[1] = X[1]$ phải ràng buộc là khi $N \gt 0$. Còn vòng lặp xét $i$ từ $2$ đã có điều kiện $i \le N$, không thỏa thì vòng lặp không chạy nên chỗ này không phải lo.

Với test 1 của đề: $F[0] = 0$, $F[1] = 1$, $F[2] = \max(1,\ 0 + 2) = 2$, $F[3] = \max(2,\ 1 + 3) = 4$, $F[4] = \max(4,\ 2 + 4) = 6$, $F[5] = \max(6,\ 4 + 5) = 9$ ✅.

Minh hoạ: lấy hay bỏ quái vật i?

Các bạn nhập số vàng của các quái vật rồi bấm Tiếp để xem từng $F[i]$ được tính từ 2 lựa chọn ra sao. Ở bước cuối mình còn lần ngược lại để chỉ ra những quái vật được lấy tiền:

Số vàng X

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    // freopen("dpprincess.inp", "r", stdin);
    // freopen("dpprincess.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        long long x[n + 1], f[n + 1];
        for(int i = 1; i <= n; ++i){
            cin >> x[i];
        }
        f[0] = 0;
        if(n > 0){
            f[1] = x[1];
        }
        for(int i = 2; i <= n; ++i){
            f[i] = max(f[i - 1], f[i - 2] + x[i]);
        }
        cout << f[n] << endl;
    }
    return 0;
}

import sys
# sys.stdin = open("dpprincess.inp", "r")
# sys.stdout = open("dpprincess.out", "w")
data = sys.stdin.read().split()
pos = 0
t = int(data[pos]); pos += 1
res = []
for _ in range(t):
    n = int(data[pos]); pos += 1
    x = [0] * (n + 1)
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        x[i] = int(data[pos]); pos += 1
    f[0] = 0
    if n > 0:
        f[1] = x[1]
    for i in range(2, n + 1):
        f[i] = max(f[i - 1], f[i - 2] + x[i])
    res.append(f[n])
print("\n".join(map(str, res)))

Trong code gốc mình có 2 dòng freopen("dpprincess.inp", ...) / freopen("dpprincess.out", ...) để đọc ghi file. Khi nộp trên CLUE OJ (đọc/ghi chuẩn) thì các bạn để chúng ở dạng chú thích như trên là được; nếu đề thi yêu cầu đọc ghi file thì bỏ dấu // đi nhé.

C++▶ Chạy tay từng dòng codeCách 1: đọc hết mảng x rồi tính f[i] = max(f[i-1], f[i-2] + x[i]), in f[n].

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

Dữ liệu mẫu:

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

2using namespace std;

4int main(){

5 // freopen("dpprincess.inp", "r", stdin);

6 // freopen("dpprincess.out", "w", stdout);

7 ios::sync_with_stdio(0);

8 cin.tie(0);

9 int t;

10 cin >> t;

11 while(t--){

12 int n;

13 cin >> n;

14 long long x[n + 1], f[n + 1];

15 for(int i = 1; i <= n; ++i){

16 cin >> x[i];

17 }

18 f[0] = 0;

19 if(n > 0){

20 f[1] = x[1];

21 }

22 for(int i = 2; i <= n; ++i){

23 f[i] = max(f[i - 1], f[i - 2] + x[i]);

24 }

25 cout << f[n] << endl;

26 }

27 return 0;

28}

Giải thích 1 số chỗ trong cách làm ở trên:

2 dòng đầu của hàm main (ios::sync_with_stdio(0); cin.tie(0);) giúp đẩy nhanh tốc độ nhập xuất nếu các bạn code C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là ra rất nhiều bài viết giải thích nhé). Kinh nghiệm là bài nào cần nhập xuất nhiều thì ta nên thêm 2 dòng này vào đầu hàm main cho chạy nhanh hơn. Nếu code theo C thì chẳng cần, nhưng thường lập trình thi đấu ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó.
Do bài này vị trí tính từ 1, để thống nhất tránh rắc rối không cần thiết ta khởi tạo mảng $X$, $F$ có $n + 1$ phần tử để chỉ số chạy từ $0$ đến $n$; coi như bỏ qua không xài chỉ số $0$ của $X$, chỉ xài từ $1$ đến $n$.
Kiểu dữ liệu: đúng ra chỉ mảng $F$ cần long long (số nguyên 8 byte), còn mảng $X$ chỉ cần int vì đề cho $0 \le x_i \le 10^9$, int chứa đủ. Mảng $F$ thì liên tục được cộng lên: chỉ cần 2 số $10^9$ cộng nhau là đã gần chạm giới hạn của int (khoảng $2.1 \cdot 10^9$), 3 số $10^9$ là vượt luôn – tràn số. Các bạn bấm nút Vàng 10^9 trong khung chạy tay để thấy $F$ lên tới $2 \cdot 10^9$ nha. Bộ nhớ thường cho rất dư dả nên mình để luôn cả $X$ là long long; lời khuyên là cứ để long long hết để tránh những tình huống bị tràn số.

Đánh giá độ phức tạp của cách làm này:

Không gian: $O(2 \cdot N)$ là tổng bộ nhớ của 2 mảng $X$, $F$, tức là $O(N)$.
Thời gian: vòng lặp xét qua $T$ test, mỗi test lặp $N$ lần để đọc mảng $X$ và $N$ lần để tạo mảng $F$, tổng là $O(T \cdot 2 \cdot N)$. Theo quy tắc nhân Big-O, hằng số nhân có thể bỏ qua nên kết luận là $O(T \cdot N)$.

Không gian$O(N)$

Thời gian$O(T \cdot N)$

Trường hợp xấu nhất $T = 10$, $N = 10^4$ thì cả thảy số lần lặp là $10 \cdot 2 \cdot 10^4 = 2 \cdot 10^5$. Ngưỡng giới hạn 1 giây là khoảng $(3 \text{ đến } 5) \cdot 10^7$, cao lắm là $10^8$, nên còn ít hơn cả 100 đến 200 lần – yên tâm không bị TLE.

Đi thi thì code vầy là đủ

Nếu gặp bài này trong phòng thi bị giới hạn thời gian thì mình sẽ code đúng như ở trên là được rồi, vì nó thể hiện tư tưởng rất trực quan, dễ cài đặt, còn thời gian làm qua bài khác. Còn nếu thoải mái thời gian thì ta thử suy nghĩ tối ưu thêm, cả về không gian lẫn thời gian – xem 2 cách tiếp theo nhé.

Cách 2Gộp đọc dữ liệu và xử lý, bỏ mảng X – O(T·N)

Nếu các bạn để ý sẽ thấy: trước bước tạo mảng $F$, ta có một vòng lặp đọc giá trị vào mảng $X$ từ $X[1]$ đến $X[N]$. Rồi tới bước tạo mảng $F$ ta lặp $i$ từ $2$ đến $N$, lúc này mảng $X$ chỉ được gọi duy nhất ở $X[i]$, tức là lần lượt $X[2], X[3], \ldots, X[N]$ (còn $X[1]$ đã gán cho $F[1]$ ở bước khởi tạo cơ sở). Mỗi giá trị được dùng đúng 1 lần, đúng theo thứ tự đọc vào.

Ý tưởng

Gộp 2 vòng lặp (đọc $X$ và tính $F$) làm 1. Không cần mảng $X$ nữa: dùng 1 biến x (không phải mảng, chỉ là 1 biến thôi) đọc từ input vào rồi xử lý luôn. Cả thảy đỡ được $O(N)$ bộ nhớ và $O(N)$ thời gian.

Chỗ if(n > 0){ cin >> f[1]; }: theo lẽ ra phải đọc vào biến x (cin >> x;) rồi mới gán f[1] = x;, thì thay vì làm 2 bước như vậy ta đọc thẳng giá trị từ input vào f[1] luôn cho khỏe.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    // freopen("dpprincess.inp", "r", stdin);
    // freopen("dpprincess.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        long long x, f[n + 1];
        f[0] = 0;
        if(n > 0){
            cin >> f[1];
        }
        for(int i = 2; i <= n; ++i){
            cin >> x;
            f[i] = max(f[i - 1], f[i - 2] + x);
        }
        cout << f[n] << endl;
    }
    return 0;
}

import sys
# sys.stdin = open("dpprincess.inp", "r")
# sys.stdout = open("dpprincess.out", "w")
data = sys.stdin.read().split()
pos = 0
t = int(data[pos]); pos += 1
res = []
for _ in range(t):
    n = int(data[pos]); pos += 1
    f = [0] * (n + 1)
    f[0] = 0
    if n > 0:
        f[1] = int(data[pos]); pos += 1
    for i in range(2, n + 1):
        x = int(data[pos]); pos += 1
        f[i] = max(f[i - 1], f[i - 2] + x)
    res.append(f[n])
print("\n".join(map(str, res)))

C++▶ Chạy tay từng dòng codeCách 2: đọc x tới đâu tính f[i] tới đó, không cần mảng x.

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

Dữ liệu mẫu:

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

2using namespace std;

4int main(){

5 // freopen("dpprincess.inp", "r", stdin);

6 // freopen("dpprincess.out", "w", stdout);

7 ios::sync_with_stdio(0);

8 cin.tie(0);

9 int t;

10 cin >> t;

11 while(t--){

12 int n;

13 cin >> n;

14 long long x, f[n + 1];

15 f[0] = 0;

16 if(n > 0){

17 cin >> f[1];

18 }

19 for(int i = 2; i <= n; ++i){

20 cin >> x;

21 f[i] = max(f[i - 1], f[i - 2] + x);

22 }

23 cout << f[n] << endl;

24 }

25 return 0;

26}

Đánh giá độ phức tạp của cách làm này:

Không gian: $O(N)$ cho mảng $F$ (đỡ được một mảng so với cách 1).
Thời gian: mỗi test chỉ còn 1 vòng lặp $N$ lần, tổng $O(T \cdot N)$ (đỡ được $O(N)$ thao tác mỗi test).

Không gian$O(N)$

Thời gian$O(T \cdot N)$

Cách 3Chỉ dùng 3 biến – bộ nhớ O(1)

Thậm chí còn 1 chỗ nữa có thể tối ưu, nhưng là tối ưu về mặt bộ nhớ thôi chứ về mặt thời gian không thay đổi (thậm chí có phần tệ hơn một chút, nên các bạn cân nhắc khi sử dụng).

Các bạn thấy $F[i]$ chỉ gọi lại $F[i-1]$ và $F[i-2]$, nghĩa là chỉ cần 2 giá trị liền trước. Nên ta có thể tạo 3 biến f0, f1, fn với ý nghĩa: f0 đóng vai $F[i-2]$, f1 đóng vai $F[i-1]$, còn fn chính là $F[i]$.

Ban đầu cũng gán f0 = 0, f1 = X[1].
Tính fn = max(f1, f0 + x), xong thì "dời" cả bộ sang phải 1 ô trước khi vòng lặp xét giá trị $i$ mới: f0 = f1; f1 = fn;.
Do cập nhật liên tục như vậy nên sang lần lặp sau, f0, f1 luôn đảm bảo là 2 giá trị liền trước của fn ngay thời điểm đó.

Vì sao phải gán fn ở bước khởi tạo?

Các bạn thấy ở bước gán f0 = 0 thì ta cũng gán fn = f0, và lúc đọc dữ liệu vào f1 thì ta cũng gán fn = f1. Lý do là lỡ như $n$ là $0$ hay $1$ thì vòng lặp for sẽ không chạy vào để tính fn, mà in ra một biến chưa có giá trị thì sẽ ra kết quả "rác". Gán như vậy thì sau cùng in fn: $n = 0$ sẽ in giá trị của f0, $n = 1$ in giá trị của f1, còn $n \ge 2$ thì in fn tương ứng. Các bạn thử nút N = 0 và N = 1 trong khung chạy tay nhé.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    // freopen("dpprincess.inp", "r", stdin);
    // freopen("dpprincess.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        long long x, f0, f1, fn;
        fn = f0 = 0;
        if(n > 0){
            cin >> f1;
            fn = f1;
        }
        for(int i = 2; i <= n; ++i){
            cin >> x;
            fn = max(f1, f0 + x);
            f0 = f1;
            f1 = fn;
        }
        cout << fn << endl;
    }
    return 0;
}

import sys
# sys.stdin = open("dpprincess.inp", "r")
# sys.stdout = open("dpprincess.out", "w")
data = sys.stdin.read().split()
pos = 0
t = int(data[pos]); pos += 1
res = []
for _ in range(t):
    n = int(data[pos]); pos += 1
    fn = f0 = 0
    f1 = 0
    if n > 0:
        f1 = int(data[pos]); pos += 1
        fn = f1
    for i in range(2, n + 1):
        x = int(data[pos]); pos += 1
        fn = max(f1, f0 + x)
        f0 = f1
        f1 = fn
    res.append(fn)
print("\n".join(map(str, res)))

C++▶ Chạy tay từng dòng codeCách 3: chỉ giữ f0 = F[i-2], f1 = F[i-1], fn = F[i] rồi dời dần sang phải.

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

Dữ liệu mẫu:

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

2using namespace std;

4int main(){

5 // freopen("dpprincess.inp", "r", stdin);

6 // freopen("dpprincess.out", "w", stdout);

7 ios::sync_with_stdio(0);

8 cin.tie(0);

9 int t;

10 cin >> t;

11 while(t--){

12 int n;

13 cin >> n;

14 long long x, f0, f1, fn;

15 fn = f0 = 0;

16 if(n > 0){

17 cin >> f1;

18 fn = f1;

19 }

20 for(int i = 2; i <= n; ++i){

21 cin >> x;

22 fn = max(f1, f0 + x);

23 f0 = f1;

24 f1 = fn;

25 }

26 cout << fn << endl;

27 }

28 return 0;

29}

Đánh giá độ phức tạp của cách làm này:

Không gian: $O(1)$ – chỉ còn vài biến, không còn mảng nào.
Thời gian: vẫn $O(T \cdot N)$. Thậm chí có thể thấy là tệ hơn một chút vì mỗi bước lặp phải làm thêm 2 phép gán (f0 = f1; f1 = fn;): lặp $T \cdot N$ lần là làm thêm $2 \cdot T \cdot N$ phép gán, trường hợp xấu nhất $T = 10$, $N = 10^4$ là thêm $2 \cdot 10^5$ (200,000) phép gán. Trong khi dùng mảng $F$ thì không cần gán như vậy, cứ gọi $F[i-1]$, $F[i-2]$ là lấy ra được vì đã lưu trữ lại.

Không gian$O(1)$

Thời gian$O(T \cdot N)$

Có nên tối ưu tới mức này?

Thiết nghĩ đa phần các bài giải thuật thì yếu tố thời gian quan trọng hơn, còn bộ nhớ lúc nào cũng dư dả thoải mái, nên việc tối ưu này là không cần thiết nhé các bạn. Mình cứ nói ra để các bạn thấy được, để trong tình huống đặc biệt cần tối ưu bộ nhớ (ví dụ ai đó thử thách các bạn chẳng hạn hehe 😁) thì các bạn vẫn biết chỗ mà tối ưu.

Ghi chú của mình: code C++ và Python của cả 3 cách đều cho đúng output của ví dụ đề, và đã được so với code vét cạn (thử mọi cách chọn quái vật không liền kề) trên 400 bộ test ngẫu nhiên nhỏ ($t \le 10$, $0 \le N \le 12$, có cả số vàng tới $10^9$ và test $N = 0$) – khớp hết. Với test lớn nhất $T = 10$, $N = 10^4$, vàng ngẫu nhiên tới $10^9$: bản C++ của cả 3 cách đều chạy khoảng 0.1 giây, bản Python khoảng 0.5 giây.

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 😇

Lập Trình Thuật Toán

Công Chúa (DPPRINCESS)

Đề bài

Lời mở đầu

Cách 1Quy hoạch động 4 bước – O(T·N)

Bước 1: Xác định bài toán con

Bước 2: Xác định bài toán cơ sở

Bước 3: Xác định đáp án bài toán

Bước 4: Xác định công thức truy hồi

Minh hoạ: lấy hay bỏ quái vật i?

Cách 2Gộp đọc dữ liệu và xử lý, bỏ mảng X – O(T·N)

Cách 3Chỉ dùng 3 biến – bộ nhớ O(1)

Nhận xét

Đăng nhận xét

Dữ liệu trang web (tự động – không xoá)

Hướng dẫn tham gia Thi thử HSG Tin học hàng tuần trên ClueOJ (từ đăng ký tài khoản đến lúc vào phòng thi)

Khóa học luyện thi chuyên Tin, HSG Tin học – lập trình thuật toán C++