Gián Ăn

Nguồn: Bài tập QHĐ (không rõ OJ) Độ khó: Dễ Quy hoạch động QHĐ trên lưới Vét cạn

Đề bài

Gián – Ăn  ·  Giới hạn thời gian: 1.0 giây  ·  Giới hạn bộ nhớ: 128 megabyte

Trên một lưới ô vuông hình chữ nhật $M \times N$, tại mỗi ô $(i; j)$ của lưới ta đặt một lượng thức ăn dành cho gián, tương ứng với số nguyên dương $a_{ij}$. Từ ô hiện tại, gián có thể bò đến một trong 2 ô khác để ăn hết lượng thức ăn đặt ở ô đó là: ô kề cạnh bên phải và ô kề cạnh bên dưới. Ban đầu chú gián ở vị trí ô $(1; 1)$ và giả thiết ô này không chứa thức ăn.

Yêu cầu: Hãy xác định lộ trình trong lưới của gián sao cho từ ô xuất phát đi đến ô cuối cùng $(M; N)$, gián có thể ăn được một lượng thức ăn nhiều nhất.

Dữ liệu vào:

• Dòng đầu ghi hai số nguyên dương $M$ và $N$ $(0 \lt M, N \le 100)$.
• $M$ dòng tiếp theo, mỗi dòng thứ $i$ ghi $N$ số nguyên dương $a_{ij}$ $(0 \le a_{ij} \le 100;\ i = 1..M;\ j = 1..N)$.

Dữ liệu ra: Đưa ra màn hình một số nguyên, là lượng thức ăn lớn nhất mà gián có thể ăn được.

Ví dụ 1 – input

4 5
0 5 1 3 4
6 1 9 1 5
1 1 1 4 1
1 3 4 6 3

Ví dụ 1 – output

30

Ví dụ 2 – input

4 5
0 1 2 3 1
0 2 3 4 5
6 1 2 3 1
3 2 4 1 5

Ví dụ 2 – output

21

Lời mở đầu

Mình luôn khuyên các bạn là với mọi bài tập, nếu chưa nghĩ ra cách làm tối ưu, hoặc nghĩ ra rồi mà chưa chắc chắn về độ chính xác, thì trước tiên hãy giải bài đó theo cách vét cạn đi. Cách vét cạn (cài đặt đúng) luôn cho ra kết quả đúng, chỉ có cái là chạy lâu thôi – thì ta lợi dụng nó để kiểm tra tính chính xác cho cách tối ưu làm sau đó. Làm vét cạn rồi các bạn cũng sẽ nhìn ra những chỗ chưa tốt của nó, làm tiền đề để tối ưu. Còn nếu sau cùng vẫn không nghĩ ra cách tối ưu thì cách vét cạn sẽ giúp các bạn vét được bao nhiêu điểm thì vét (thi theo thể thức IOI thì đúng test nào có điểm test đó, còn thể thức ACM phải đúng hết mới AC thì… thua rồi hihi 😅).

Bài này hiện chưa có link nộp, các bạn có thể chạy thử code ở trang Chạy code online của blog với các test ví dụ nhé.

Mình giải thích ví dụ 1 để bạn nào chưa hiểu đề sẽ hiểu rõ. Gián xuất phát ở ô góc trên trái (ô này bằng 0 – không có thức ăn), mỗi bước chỉ được sang phải hoặc xuống dưới, và phải về tới ô góc dưới phải. Đi qua ô nào thì ăn hết thức ăn ô đó. Một lộ trình tốt nhất là:

0 → 6 (xuống) → 1 (phải) → 9 (phải) → 1 (phải) → 4 (xuống) → 6 (xuống) → 3 (phải)

Tổng $6 + 1 + 9 + 1 + 4 + 6 + 3 = 30$, không có lộ trình nào ăn được nhiều hơn → đáp án 30. Ví dụ 2 tương tự, đáp án là $21$ (ví dụ: $0 \to 0 \to 6 \to 3 \to 2 \to 4 \to 1 \to 5$ hoặc $0 \to 1 \to 2 \to 3 \to 4 \to 5 \to 1 \to 5$ đều được $21$).

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 1Vét cạn liệt kê mọi đường đi · TLE/MLECách 2Quy hoạch động trên lưới O(M·N)

Cách 1Vét cạn – liệt kê mọi lộ trình

Cách làm vét cạn là sao? Từ vị trí xuất phát của con gián $(1, 1)$ ta liệt kê ra mọi phương án có thể đi để đến được ô $(M, N)$. Với mỗi phương án ta tính số lượng thức ăn thu được, và sau cùng lấy lớn nhất.

Ví dụ ma trận $3 \times 3$ như sau (con gián ở ô số 0, cần đến ô số 8):

012345678

Đi đúng quy tắc đề bài thì có cả thảy 6 phương án:

1) 0 → 1 → 2 → 5 → 8  = 16

2) 0 → 3 → 4 → 5 → 8  = 20

3) 0 → 1 → 4 → 5 → 8  = 18

4) 0 → 3 → 6 → 7 → 8  = 24 ← lớn nhất

5) 0 → 3 → 4 → 7 → 8  = 22

6) 0 → 1 → 4 → 7 → 8  = 20

Vậy đáp án của ma trận này là $24$.

Làm sao liệt kê được các phương án?

Đánh chỉ số dòng, cột từ 0 (ô đầu là $(0, 0)$, ô đích là $(M-1, N-1)$). Ta dùng một mảng 2 chiều b để lưu các phương án: mỗi dòng là 1 phương án, mỗi phần tử trong dòng là một tọa độ con gián đi qua.

• Ban đầu b chỉ có 1 dòng gồm đúng tọa độ $(0, 0)$.
• Ta xét dòng thứ idx (bắt đầu idx = 0), lấy tọa độ cuối cùng của dòng đó:
  • Nếu nó đã là ô đích → phương án này xong, tăng idx++ xét dòng tiếp theo.
  • Nếu đi được cả sang phải và xuống dưới → sao chép dòng hiện tại thành 1 dòng mới ở cuối b, thêm ô bên dưới vào cuối dòng mới; còn dòng hiện tại thì thêm ô bên phải vào cuối.
  • Nếu chỉ còn 1 lựa chọn (ở cột cuối thì chỉ xuống, ở dòng cuối thì chỉ sang phải) → không cần tạo dòng mới, thêm thẳng ô đó vào cuối dòng hiện tại.
• Khi idx bằng số dòng của b thì đã hết phương án.

Với ma trận $3 \times 3$, vài bước đầu diễn ra như sau:

Thời điểm	Mảng b
Ban đầu	(0,0)
Từ (0,0) đi được 2 hướng: sao chép dòng, dòng mới thêm ô dưới, dòng cũ thêm ô phải	(0,0) (0,1) (0,0) (1,0)
Vẫn xét dòng 0, từ (0,1) đi được 2 hướng	(0,0) (0,1) (0,2) (0,0) (1,0) (0,0) (0,1) (1,1)
Từ (0,2) chỉ xuống được, rồi từ (1,2) cũng chỉ xuống được → tới đích, idx++	(0,0) (0,1) (0,2) (1,2) (2,2) (0,0) (1,0) (0,0) (0,1) (1,1)
Sau khi xét hết các dòng	(0,0) (0,1) (0,2) (1,2) (2,2) (0,0) (1,0) (1,1) (1,2) (2,2) (0,0) (0,1) (1,1) (1,2) (2,2) (0,0) (1,0) (2,0) (2,1) (2,2) (0,0) (1,0) (1,1) (2,1) (2,2) (0,0) (0,1) (1,1) (2,1) (2,2)

Giờ chỉ cần cộng $a[i][j]$ theo từng dòng để tìm dòng có tổng lớn nhất. Thực ra cũng không cần đợi đến cuối: ta tạo thêm mảng 1 chiều res chạy song song với b – res[idx] là tổng thức ăn của phương án idx tính đến lúc đó. Mỗi khi thêm ô vào dòng idx thì cộng giá trị ô đó vào res[idx]; khi sao chép dòng thì res cũng thêm phần tử mới bằng res[idx] cộng giá trị ô bên dưới. Khi một dòng tới đích thì so res[idx] với Max để cập nhật.

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;

struct Point{
    int x, y;
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m, n;
    cin >> m >> n;
    int a[m][n];
    for(int i = 0; i < m; ++i){
        for(int j = 0; j < n; ++j){
            cin >> a[i][j];
        }
    }
    vector<vector<Point>> b;
    vector<Point> temp;
    Point p;
    p.x = p.y = 0;
    temp.push_back(p);
    b.push_back(temp);
    int idx = 0;
    vector<int> res;
    res.push_back(0);
    int Max = -1;
    while(idx < (int)b.size()){
        int j = (int)b[idx].size() - 1;
        if(b[idx][j].x == m - 1 && b[idx][j].y == n - 1){
            Max = max(Max, res[idx]);
            idx++;
            continue;
        }
        if(b[idx][j].x + 1 < m && b[idx][j].y + 1 < n){
            temp = b[idx];
            p.x = b[idx][j].x + 1;
            p.y = b[idx][j].y;
            temp.push_back(p);
            b.push_back(temp);
            res.push_back(res[idx] + a[p.x][p.y]);
            p.x = b[idx][j].x;
            p.y = b[idx][j].y + 1;
            b[idx].push_back(p);
            res[idx] += a[p.x][p.y];
        }
        else if(b[idx][j].x + 1 < m){
            p.x = b[idx][j].x + 1;
            p.y = b[idx][j].y;
            b[idx].push_back(p);
            res[idx] += a[p.x][p.y];
        }
        else if(b[idx][j].y + 1 < n){
            p.x = b[idx][j].x;
            p.y = b[idx][j].y + 1;
            b[idx].push_back(p);
            res[idx] += a[p.x][p.y];
        }
    }
    cout << Max;
    return 0;
}

import sys

def main():
    data = sys.stdin.read().split()
    m, n = int(data[0]), int(data[1])
    a = []
    p = 2
    for i in range(m):
        a.append([int(x) for x in data[p:p + n]])
        p += n
    b = [[(0, 0)]]          # mỗi dòng là một phương án đi
    res = [0]               # res[idx] = tổng thức ăn của phương án idx
    idx = 0
    Max = -1
    while idx < len(b):
        x, y = b[idx][-1]
        if x == m - 1 and y == n - 1:
            Max = max(Max, res[idx])
            idx += 1
            continue
        if x + 1 < m and y + 1 < n:
            temp = b[idx][:]
            temp.append((x + 1, y))
            b.append(temp)
            res.append(res[idx] + a[x + 1][y])
            b[idx].append((x, y + 1))
            res[idx] += a[x][y + 1]
        elif x + 1 < m:
            b[idx].append((x + 1, y))
            res[idx] += a[x + 1][y]
        elif y + 1 < n:
            b[idx].append((x, y + 1))
            res[idx] += a[x][y + 1]
    print(Max)

main()

Giải thích một số chỗ:

• ios::sync_with_stdio(0); cin.tie(0); giúp tăng tốc nhập xuất của C++ – bài này input có thể tới $10\,000$ số nên nên thêm vào.
• b là mảng 2 chiều lưu các phương án; res lưu tổng thức ăn của từng phương án, luôn cập nhật đồng thời với b; temp là mảng tạm để sao chép dòng; p lưu tọa độ ô bên phải / bên dưới sẽ được thêm vào.
• Max = -1 để lần so sánh đầu tiên chắc chắn được cập nhật.
• Trong vòng while: j là vị trí tọa độ cuối của dòng idx; if đầu kiểm tra đã tới đích chưa; if thứ hai là trường hợp đi được cả 2 hướng (tạo dòng mới); 2 else if còn lại là chỉ có 1 lựa chọn.

Các bạn chạy tay từng dòng code này với lưới nhỏ để thấy mảng b "đẻ" thêm dòng như thế nào (dòng viền tím là dòng vừa được sao chép ra):

C++▶ Chạy tay từng dòng codeVét cạn: mỗi dòng của b là một lộ trình, gặp ngã rẽ thì sao chép dòng. Chỉ dùng được với lưới rất nhỏ.

Dữ liệu vào (stdin) – sửa thoải mái3 3 0 1 2 3 4 5 6 7 8

Dữ liệu mẫu:

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

2using namespace std;

3

4struct Point{

5 int x, y;

6};

7

8int main(){

9 ios::sync_with_stdio(0);

10 cin.tie(0);

11 int m, n;

12 cin >> m >> n;

13 int a[m][n];

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

15 for(int j = 0; j < n; ++j){

16 cin >> a[i][j];

17 }

18 }

19 vector<vector<Point>> b;

20 vector<Point> temp;

21 Point p;

22 p.x = p.y = 0;

23 temp.push_back(p);

24 b.push_back(temp);

25 int idx = 0;

26 vector<int> res;

27 res.push_back(0);

28 int Max = -1;

29 while(idx < (int)b.size()){

30 int j = (int)b[idx].size() - 1;

31 if(b[idx][j].x == m - 1 && b[idx][j].y == n - 1){

32 Max = max(Max, res[idx]);

33 idx++;

34 continue;

35 }

36 if(b[idx][j].x + 1 < m && b[idx][j].y + 1 < n){

37 temp = b[idx];

38 p.x = b[idx][j].x + 1;

39 p.y = b[idx][j].y;

40 temp.push_back(p);

41 b.push_back(temp);

42 res.push_back(res[idx] + a[p.x][p.y]);

43 p.x = b[idx][j].x;

44 p.y = b[idx][j].y + 1;

45 b[idx].push_back(p);

46 res[idx] += a[p.x][p.y];

47 }

48 else if(b[idx][j].x + 1 < m){

49 p.x = b[idx][j].x + 1;

50 p.y = b[idx][j].y;

51 b[idx].push_back(p);

52 res[idx] += a[p.x][p.y];

53 }

54 else if(b[idx][j].y + 1 < n){

55 p.x = b[idx][j].x;

56 p.y = b[idx][j].y + 1;

57 b[idx].push_back(p);

58 res[idx] += a[p.x][p.y];

59 }

60 }

61 cout << Max;

62 return 0;

63}

ChậmVừaNhanhRất nhanh

Đánh giá cách làm này: chắc chắn với dữ liệu nhỏ nó sẽ chạy ra kết quả đúng, còn khi dữ liệu lớn thì phải chờ rất lâu, nộp bài khả năng lớn là bị TLE. Thậm chí mình nộp thử thì tại test case 5 bị lỗi MLE (Memory Limit Exceeded – quá giới hạn bộ nhớ) luôn, vì mảng b lưu quá nhiều phương án. Số phương án với ma trận vuông $k \times k$:

1 x 11

2 x 22

3 x 36

4 x 420

5 x 570

6 x 6252

7 x 7924

8 x 83 432

9 x 912 870

10 x 1048 620

Cứ tăng kích thước thêm 1 thì số phương án tăng gần gấp 4 (cỡ 3.7 lần) – tăng theo cấp lũy thừa, vì tại mỗi ô có 2 lựa chọn, mỗi lựa chọn lại có 2 lựa chọn nữa… Thực ra đây chính là tổ hợp $\binom{M + N - 2}{M - 1}$ (chọn $M - 1$ bước "xuống" trong tổng số $M + N - 2$ bước). Với $100 \times 100$ thì số phương án là $\binom{198}{99} \approx 2.3 \cdot 10^{58}$ – một số có tới 59 chữ số (9 chữ số đã là hàng tỷ rồi nha các bạn!). Chắc chắn chẳng thể chạy nổi, bộ nhớ 128 MB cũng chẳng chứa nổi.

Không gian$O\!\left(\binom{M+N-2}{M-1} \cdot (M+N)\right)$

Thời gian$O\!\left(\binom{M+N-2}{M-1} \cdot (M+N)\right)$

Chỉ dùng để đối chiếu

Cách vét cạn này chỉ để chạy test dữ liệu nhỏ, kiểm tra tính chính xác cho cách tối ưu thôi, nộp bài là không được. Nhưng kể cả cách vét cạn, khi mình trao đổi với một số bạn học viên thì cũng có bạn không code ra được, nên mình trình bày trước để bạn nào chưa làm được thì tham khảo nhé.

Cách 2Quy hoạch động trên lưới – O(M·N)

Liệt kê tất cả các phương án chắc chắn không ổn. Để nhìn ra cách tối ưu, các bạn để ý: để đến được ô $(i, j)$, ngay trước đó con gián chỉ có thể đứng ở ô trên $(i - 1, j)$ hoặc ô bên trái $(i, j - 1)$ – vì quy luật đi là sang phải hoặc xuống dưới nên ta "phủ định" lại thôi.

Điểm dở của vét cạn là các phương án trùng lấp nhau rất nhiều (ví dụ ở lưới $3 \times 3$, đoạn $(1,1) \to (1,2) \to (2,2)$ bị tính đi tính lại ở 2 phương án). Sẽ tối ưu hơn nếu với mỗi ô ta chỉ lưu lượng thức ăn lớn nhất mà gián ăn được từ đầu đến ô đó. Khi đó, muốn tới $(i, j)$ thì xem 2 ô trên / trái ô nào có giá trị lớn hơn, lấy giá trị đó cộng với thức ăn tại $(i, j)$ là xong. Cứ tính lần lượt như thế, đáp án nằm ở ô $(M, N)$.

Đây chính là tư tưởng Quy Hoạch Động. Theo 4 bước giải một bài toán quy hoạch động:

• Bước 1 – Bài toán con: Gọi $F[i][j]$ là lượng thức ăn lớn nhất mà gián ăn được khi đi từ ô $(1, 1)$ đến ô $(i, j)$.
• Bước 2 – Bài toán cơ sở: $F[1][1] = 0$ (ô xuất phát không có thức ăn). Dòng đầu tiên là mảng cộng dồn: $F[1][j] = a[1][1] + a[1][2] + \ldots + a[1][j]$, vì các ô ở dòng đầu chỉ có thể đến từ bên trái (không có dòng nào bên trên). Tương tự cột đầu tiên chỉ có thể đến từ trên xuống.
• Bước 3 – Đáp án: $F[M][N]$ – lượng thức ăn lớn nhất thu được từ đầu đến ô đích.
• Bước 4 – Công thức truy hồi: $F[i][j] = a[i][j] + \max(F[i - 1][j],\ F[i][j - 1])$.

Mẹo: thêm 1 dòng 0 và 1 cột 0 làm "lính canh"

Tạo mảng dư thêm dòng $0$ và cột $0$, toàn bộ bằng $0$. Khi gọi tới $F[i - 1][j]$ hay $F[i][j - 1]$ nằm ngoài lưới thì nó chỉ là $0$ – nhỏ nhất rồi (vì $a_{ij} \ge 0$) nên coi như không có, không ảnh hưởng kết quả. Nhờ vậy dòng đầu, cột đầu tự động thành cộng dồn mà không phải viết if kiểm tra ô hợp lệ.

Hơn nữa, $F[i][j]$ được tính lần lượt từ trái qua phải, từ trên xuống dưới – trùng đúng thứ tự dữ liệu đọc vào. Nên ta chỉ cần một mảng a: đọc giá trị ô vào biến tạm x rồi ghi luôn a[i][j] = x + max(a[i-1][j], a[i][j-1]).

Minh hoạ điền bảng QHĐ

Em nhập lưới (mỗi dòng của lưới cách nhau bởi dấu ; hoặc xuống dòng) rồi bấm Tiếp để xem từng ô được tính: ô vàng là ô đang tính, ô tím là ô được chọn (lớn hơn trong 2 ô trên/trái). Bước cuối dò ngược để tô lộ trình tốt nhất.

Lưới

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(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m, n;
    cin >> m >> n;
    int a[m + 1][n + 1];
    for(int i = 0; i <= m; ++i){
        for(int j = 0; j <= n; ++j){
            if(i == 0 || j == 0){
                a[i][j] = 0;
            }
            else{
                int x;
                cin >> x;
                a[i][j] = x + max(a[i - 1][j], a[i][j - 1]);
            }
        }
    }
    cout << a[m][n];
    return 0;
}

import sys

def main():
    data = sys.stdin.read().split()
    m, n = int(data[0]), int(data[1])
    a = [[0] * (n + 1) for _ in range(m + 1)]
    p = 2
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            x = int(data[p]); p += 1
            a[i][j] = x + max(a[i - 1][j], a[i][j - 1])
    print(a[m][n])

main()

Dòng if(i == 0 || j == 0) trong vòng lặp gán $0$ cho toàn bộ dòng đầu và cột đầu (lính canh). Còn lại (chỉ số từ 1 trở đi) thì đọc x từ input, cộng với giá trị lớn hơn của a[i - 1][j] và a[i][j - 1] rồi ghi lại vào a[i][j]. Kết thúc vòng lặp thì in a[m][n]. Bạn nào đọc tới đây mà vẫn chưa rõ vì sao ra đáp án thì chạy tay 2 ví dụ của đề với khung bên dưới là sẽ rõ ngay:

C++▶ Chạy tay từng dòng codeQHĐ O(M·N): đọc tới đâu tính tới đó, a[i][j] = x + max(ô trên, ô trái).

Dữ liệu vào (stdin) – sửa thoải mái4 5 0 5 1 3 4 6 1 9 1 5 1 1 1 4 1 1 3 4 6 3

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 int m, n;

8 cin >> m >> n;

9 int a[m + 1][n + 1];

10 for(int i = 0; i <= m; ++i){

11 for(int j = 0; j <= n; ++j){

12 if(i == 0 || j == 0){

13 a[i][j] = 0;

14 }

15 else{

16 int x;

17 cin >> x;

18 a[i][j] = x + max(a[i - 1][j], a[i][j - 1]);

19 }

20 }

21 }

22 cout << a[m][n];

23 return 0;

24}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(M \cdot N)$ với $M$ là số dòng, $N$ là số cột.
• Thời gian: $O(M \cdot N)$ – mỗi ô chỉ tính đúng 1 lần.

Không gian$O(M \cdot N)$

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

Đây chắc chắn là cách tối ưu nhất rồi: bài nào cũng tối thiểu phải đọc hết dữ liệu vào, mà ở đây ta xử lý luôn ngay khi đọc, đọc xong là có đáp án. Trường hợp lớn nhất $100 \times 100$ chỉ lặp khoảng $10^4$ lần, quá nhỏ so với giới hạn cỡ $(3 \div 5) \cdot 10^7$ hay cao lắm $10^8$ phép tính mỗi giây.

Thấy cái hay của giải thuật chưa?

Từ số phương án có tới cỡ 59 chữ số (tỷ tỷ tỷ tỷ tỷ tỷ…) rút xuống chỉ còn $10^4$ lần lặp – tối ưu hơn rất nhiều đúng không nè 😍. Kết quả lớn nhất cũng chỉ cỡ $199 \cdot 100 \lt 2 \cdot 10^4$ nên kiểu int là thoải mái.

Ghi chú của mình: code C++ và Python của cả 2 cách đã chạy đúng 2 test của đề, và được so khớp với một code vét cạn đệ quy độc lập trên 400 bộ test ngẫu nhiên (lưới tới $6 \times 6$) – khớp hết. Với lưới $100 \times 100$, cách 2 chạy tức thì (C++ khoảng 0.03 giây, Python khoảng 0.2 giây). Cách 1 thì đúng như mình nói: lưới $12 \times 12$ (705 432 phương án) đã ngốn khoảng 270 MB bộ nhớ – vượt 128 MB, còn lưới $13 \times 13$ thì tốn hơn 1 GB và chạy khoảng 7 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 😇