Trò Chơi (DPRCDIE)

Nguồn: VinhDinhCoder Độ khó: Khá Quy hoạch động QHĐ đổi biến số

Đề bài

DPRCDIE – Trò chơi

Trò chơi rất đơn giản. Ban đầu, bạn có lượng máu $H$ và lượng giáp $A$. Bất cứ lúc nào bạn cũng có thể sống ở bất kỳ nơi nào trong ba nơi – lửa, nước và không khí. Sau mỗi đơn vị thời gian, bạn phải thay đổi nơi sinh sống. Ví dụ, nếu bạn hiện đang sống trong lửa, bạn có thể bước vào nước hoặc không khí.

• Nếu bạn bước vào không khí, sức khỏe của bạn tăng thêm 3 và áo giáp của bạn tăng thêm 2.
• Nếu bạn bước xuống nước, sức khỏe của bạn giảm 5 và áo giáp của bạn giảm 10.
• Nếu bạn bước vào lửa, sức khỏe của bạn giảm 20 và áo giáp của bạn tăng thêm 5.
• Nếu sức khỏe hoặc áo giáp của bạn trở thành $\le 0$, bạn sẽ chết ngay lập tức.

Tìm thời gian tối đa bạn có thể sống sót.

Dữ liệu nhập:

• Dòng đầu tiên bao gồm một số nguyên $t$, số lượng các trường hợp thử nghiệm.
• Đối với mỗi trường hợp thử nghiệm, sẽ có hai số nguyên dương biểu thị sức khỏe ban đầu $H$ và áo giáp ban đầu $A$.

Kết quả:

• Đối với mỗi trường hợp thử nghiệm, hãy tìm thời gian tối đa bạn có thể sống sót.
• Lưu ý: Bạn có thể chọn bất kỳ vị trí nào trong 3 vị trí trong lần di chuyển đầu tiên của bạn.

Các ràng buộc: $1 \le t \le 10$; $1 \le H, A \le 1000$.

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

Ví dụ – input

3
2 10
4 4
20 8

Ví dụ – output

1
1
5

Lời mở đầu

Bữa giờ mấy bài mình đăng có vẻ quá dễ dàng, chưa thỏa mãn với một số bạn, thì giờ đây mình sẽ cố gắng đăng thêm những bài nâng cao hơn để các bạn được thỏa mãn nhé hehe 😎.

Bài này dành cho bạn đã biết quy hoạch động

Mình nói trước là bài này chỉ phù hợp với bạn nào đã có kiến thức về quy hoạch động, cụ thể là quy hoạch động đổi biến số. Bạn nào chưa rành kiến thức này thì nên bỏ qua vì đọc có thể sẽ bị tẩu hỏa nhập ma đấy 😂 mình không chịu trách nhiệm đâu nha. Cũng vì vậy mà mình sẽ không giải thích những cái quá cơ bản như mọi khi.

Tóm tắt hiệu ứng của 3 môi trường (mỗi đơn vị thời gian bắt buộc phải chuyển sang môi trường khác):

☁️ Không khíMáu $+3$, giáp $+2$

💧 NướcMáu $-5$, giáp $-10$

🔥 LửaMáu $-20$, giáp $+5$

Giải thích ví dụ một chút (viết theo dạng (máu, giáp)):

• $H = 2, A = 10$: vào nước hay lửa thì máu $\le 0$ chết ngay, nên chỉ có thể vào không khí: $(5, 12)$, sống được 1 đơn vị thời gian. Tiếp theo phải sang nước (máu $5 - 5 = 0$) hoặc lửa (máu $5 - 20 \lt 0$), đều chết ⇒ đáp án 1.
• $H = 4, A = 4$: tương tự, vào không khí được $(7, 6)$; sau đó nước làm giáp $6 - 10 \lt 0$, lửa làm máu $7 - 20 \lt 0$ ⇒ đáp án 1.
• $H = 20, A = 8$: một cách đi tốt nhất là:

(20, 8)☁️→(23, 10)🔥→(3, 15)☁️→(6, 17)💧→(1, 7)☁️→(4, 9)→ nước / lửa đều chết

Sống được 5 đơn vị thời gian ⇒ đáp án 5.

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 để nhảy tới:

Cách 1Quy hoạch động đổi biến số f[i][health][state]

Cách 1Quy hoạch động đổi biến số

Nhận xét

• Về máu: chỉ có đúng 1 nơi làm máu tăng là không khí ($+3$), 2 nơi còn lại làm máu giảm, và lượng giảm ở nước ($-5$) hay lửa ($-20$) đều lớn hơn lượng tăng ở không khí. Vì không được ở không khí 2 lần liên tiếp, nên cứ qua 2 môi trường liên tiếp bất kì thì lượng máu luôn giảm. Máu tối đa là 1000, nghĩa là số lần chuyển môi trường cũng bị chặn (cỡ vài nghìn lần là cùng), và máu cũng không bao giờ vượt quá $H + 3$.
• Về giáp: giáp thì khác, nếu cứ qua lại giữa không khí và lửa thì giáp tăng mãi ($+2$, $+5$, $+2$, $+5$…). Ta rất khó biết trước giáp tối đa là bao nhiêu, nên không thể cho giáp làm một chiều của mảng quy hoạch động.

Đổi biến số

Thay vì hỏi "với (thời gian, máu, giáp, môi trường) thì có tới được không", ta đưa giáp ra làm giá trị của mảng: cùng thời gian, cùng máu, cùng môi trường thì giáp càng nhiều càng tốt (giáp nhiều hơn không bao giờ thiệt). Đây chính là quy hoạch động đổi biến số.

Công thức quy hoạch động

• Gọi $f[i][health][state]$ là lượng giáp lớn nhất có thể có khi đã đổi môi trường $i$ lần, lượng máu đang là $health$ và môi trường hiện tại là $state$ ($0$: không khí, $1$: nước, $2$: lửa). Không tới được thì $f = -1$.
• Bài toán cơ sở: vì lần đầu được chọn bất kì môi trường nào, ta coi như xuất phát ở cả 3 môi trường: $f[0][H][state] = A$ với mọi $state$. (Đứng ở nước thì lần đầu được vào không khí hoặc lửa, đứng ở không khí thì được xuống nước… gộp lại đủ cả 3 lựa chọn.)
• Đáp án: giá trị $i$ lớn nhất sao cho tồn tại $(health, state)$ để $f[i][health][state] \ne -1$.
• Chuyển trạng thái từ $f[i][health][state] = g$ sang tầng $i + 1$:
  • Đang ở không khí ($state = 0$), sang nước: máu giảm 5, giáp giảm 10, cần $health \gt 5$ và $g \gt 10$ (không được $\le 0$): $f[i+1][health-5][1] = \max(f[i+1][health-5][1],\ g - 10)$.
  • Đang ở không khí, sang lửa: cần $health \gt 20$: $f[i+1][health-20][2] = \max(f[i+1][health-20][2],\ g + 5)$.
  • Đang ở nước ($state = 1$): sang không khí ($f[i+1][health+3][0]$ với $g + 2$, luôn sống) hoặc sang lửa (như trên).
  • Đang ở lửa ($state = 2$): sang không khí hoặc sang nước, làm tương tự.

Minh hoạ bảng QHĐ theo từng tầng

Em nhập $H$, $A$ rồi bấm Tiếp để xem từng tầng $i$ của bảng: mỗi cột là một lượng máu tới được, mỗi hàng là một môi trường, số trong ô là giáp lớn nhất. Tầng cuối cùng còn ô nào đó chính là đáp án.

H A

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo những gì mình phân tích ở trên, code này mình đã AC trên web rồi nhé:

#include <bits/stdc++.h>

using namespace std;
int dp[2005][1105][3];
int numTest;
int H, A;

int main () {
    cin >> numTest;
    for (int testCase = 1; testCase <= numTest; testCase++) {
        cin >> H >> A;
        int n = 2000;
        for (int i = 0; i <= n; i++) {
            for (int health = 1; health <= H + 100; health++) {
                for (int state = 0; state <= 2; state++) {
                    dp[i][health][state] = -1;
                }
            }
        }
        dp[0][H][0] = A;
        dp[0][H][1] = A;
        dp[0][H][2] = A;
        int ans = -1;
        for (int i = 0; i < n; i++) {
            for (int health = 1; health <= H + 100; health++) {
                for (int state = 0; state <= 2; state++) {
                    if (dp[i][health][state] == -1) {
                        continue;
                    }
                    ans = i;
                    if (state == 0) {
                        if (health > 5 && dp[i][health][state] > 10) {
                            dp[i + 1][health - 5][1] = max(dp[i + 1][health - 5][1], dp[i][health][state] - 10);
                        }
                        if (health > 20) {
                            dp[i + 1][health - 20][2] = max(dp[i + 1][health - 20][2], dp[i][health][state] + 5);
                        }
                    }
                    if (state == 1) {
                        dp[i + 1][health + 3][0] = max(dp[i + 1][health + 3][0], dp[i][health][state] + 2);
                        if (health > 20) {
                            dp[i + 1][health - 20][2] = max(dp[i + 1][health - 20][2], dp[i][health][state] + 5);
                        }
                    }
                    if (state == 2) {
                        dp[i + 1][health + 3][0] = max(dp[i + 1][health + 3][0], dp[i][health][state] + 2);
                        if (health > 5 && dp[i][health][state] > 10) {
                            dp[i + 1][health - 5][1] = max(dp[i + 1][health - 5][1], dp[i][health][state] - 10);
                        }
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

import sys

def solve(H, A):
    M = H + 4  # chỉ số máu 0..H+3 (máu không bao giờ vượt quá H + 3)
    # air[h], water[h], fire[h]: giáp lớn nhất ở tầng i khi máu là h
    # và đang ở không khí / nước / lửa; -1 nghĩa là không tới được
    air = [-1] * M
    water = [-1] * M
    fire = [-1] * M
    air[H] = water[H] = fire[H] = A
    ans = -1
    i = 0
    while max(air) > 0 or max(water) > 0 or max(fire) > 0:
        ans = i
        # vào không khí (từ nước hoặc lửa): máu + 3, giáp + 2
        best = list(map(max, water[:M - 3], fire[:M - 3]))
        nair = [-1] * 3 + [v + 2 if v > 0 else -1 for v in best]
        # xuống nước (từ không khí hoặc lửa): máu - 5, giáp - 10
        best = list(map(max, air[6:], fire[6:]))
        nwater = [-1] + [v - 10 if v > 10 else -1 for v in best]
        # vào lửa (từ không khí hoặc nước): máu - 20, giáp + 5
        best = list(map(max, air[21:], water[21:]))
        nfire = [-1] + [v + 5 if v > 0 else -1 for v in best]
        air = nair
        water = (nwater + [-1] * M)[:M]
        fire = (nfire + [-1] * M)[:M]
        i += 1
    return ans

data = sys.stdin.read().split()
numTest = int(data[0])
out = []
for k in range(numTest):
    H = int(data[1 + 2 * k])
    A = int(data[2 + 2 * k])
    out.append(str(solve(H, A)))
print("\n".join(out))

Mấy phần dp[][][] trong C++ có giống trong Python không?

Có bạn hỏi mình câu này. Về ý tưởng thì giống hệt, nhưng nếu dịch nguyên mảng 3 chiều $2001 \times 1100 \times 3$ và 3 vòng lặp lồng nhau sang Python thì sẽ chạy rất chậm. Vì tầng $i + 1$ chỉ phụ thuộc tầng $i$, bản Python ở trên chỉ giữ một tầng dưới dạng 3 list air, water, fire (chỉ số là lượng máu, giá trị là giáp lớn nhất, $-1$ là không tới được), tính tầng sau bằng cách "dịch" cả list một lượt, và dừng ngay khi tầng mới không còn ô nào. Đáp án vẫn là chỉ số tầng cuối cùng còn ô.

Lưu ý nhỏ về kích thước mảng

Trong code gốc của mình, mảng được khai báo dp[2005][1100][3], mà vòng lặp health chạy tới H + 100, khi $H = 1000$ là chỉ số $1100$, vượt ra ngoài mảng 1 ô (vẫn AC vì ô đó rơi đúng vào vùng nhớ không dùng, nhưng về nguyên tắc là lỗi). Ở code trên mình sửa lại thành dp[2005][1105][3] cho an toàn, logic giữ nguyên.

C++▶ Chạy tay từng dòng codeQHĐ theo tầng i: chỉ các ô dp ≠ -1 mới được xử lý; các ô -1 (continue) và vòng khởi tạo được gom thành 1 bước.

Dữ liệu vào (stdin) – sửa thoải mái3 2 10 4 4 20 8

Dữ liệu mẫu:

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

2

3using namespace std;

4int dp[2005][1105][3];

5int numTest;

6int H, A;

7

8int main () {

9 cin >> numTest;

10 for (int testCase = 1; testCase <= numTest; testCase++) {

11 cin >> H >> A;

12 int n = 2000;

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

14 for (int health = 1; health <= H + 100; health++) {

15 for (int state = 0; state <= 2; state++) {

16 dp[i][health][state] = -1;

17 }

18 }

19 }

20 dp[0][H][0] = A;

21 dp[0][H][1] = A;

22 dp[0][H][2] = A;

23 int ans = -1;

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

25 for (int health = 1; health <= H + 100; health++) {

26 for (int state = 0; state <= 2; state++) {

27 if (dp[i][health][state] == -1) {

28 continue;

29 }

30 ans = i;

31 if (state == 0) {

32 if (health > 5 && dp[i][health][state] > 10) {

33 dp[i + 1][health - 5][1] = max(dp[i + 1][health - 5][1], dp[i][health][state] - 10);

34 }

35 if (health > 20) {

36 dp[i + 1][health - 20][2] = max(dp[i + 1][health - 20][2], dp[i][health][state] + 5);

37 }

38 }

39 if (state == 1) {

40 dp[i + 1][health + 3][0] = max(dp[i + 1][health + 3][0], dp[i][health][state] + 2);

41 if (health > 20) {

42 dp[i + 1][health - 20][2] = max(dp[i + 1][health - 20][2], dp[i][health][state] + 5);

43 }

44 }

45 if (state == 2) {

46 dp[i + 1][health + 3][0] = max(dp[i + 1][health + 3][0], dp[i][health][state] + 2);

47 if (health > 5 && dp[i][health][state] > 10) {

48 dp[i + 1][health - 5][1] = max(dp[i + 1][health - 5][1], dp[i][health][state] - 10);

49 }

50 }

51 }

52 }

53 }

54 cout << ans << endl;

55 }

56 return 0;

57}

ChậmVừaNhanhRất nhanh

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

• Không gian: mảng dp[2005][1105][3] kiểu int tốn khoảng $2005 \cdot 1105 \cdot 3 \cdot 4 \approx 26.6$ MB, thoải mái trong giới hạn 128 MB.
• Thời gian: mỗi test duyệt $n \cdot (H + 100) \cdot 3$ ô (cả lúc khởi tạo lẫn lúc QHĐ), với $n = 2000$, $H = 1000$ là khoảng $6.6 \cdot 10^6$ ô; nhân 2 bước và tối đa 10 test thì cỡ $1.3 \cdot 10^8$ phép toán rất đơn giản (phần lớn ô bằng $-1$ nên chỉ continue).

Không gian$O(n \cdot H)$

Thời gian$O(t \cdot n \cdot H)$

n = 2000 có đủ không?

Trong 2 lần đổi môi trường liên tiếp thì có tối đa 1 lần vào không khí, nên máu giảm ít nhất 2 sau mỗi 2 bước, và giáp còn bị nước "ăn" 10 mỗi lần. Thực tế mình chạy thử: với $H = A = 1000$ (lớn nhất) đáp án chỉ là 399, còn xa mới chạm $n = 2000$. Bản Python thì dừng ngay khi tầng mới trống nên không cần tới $n$.

Ghi chú của mình: code C++ đã được kiểm tra với 300 bộ test ngẫu nhiên ($H, A \le 1000$), so với một code đệ quy có nhớ thử mọi cách đi – khớp hết; bản Python được so với bản C++ trên 150 bộ test – khớp hết. Với 10 test $H = A = 1000$: bản C++ chạy khoảng 0.15 giây, bản Python khoảng 1 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 😇