Hướng giải của THẠCH SÙNG

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

🧠 Ý tưởng giải thuật: Thạch Sùng săn muỗi

🌟 Mục tiêu:

Tìm tổng số muỗi lớn nhất mà hai con Thạch Sùng có thể ăn được khi bắt đầu từ hàng đầu tiên và di chuyển xuống dưới cùng, tuân theo quy tắc di chuyển.

📋 Quy tắc:
  • Bức tường là một lưới kích thước m x n, mỗi ô chứa một số muỗi.
  • Hai con Thạch Sùng bắt đầu ở hàng đầu tiên, tại hai cột khác nhau.
  • Mỗi bước, mỗi con có thể di chuyển đến ô ở hàng kế tiếp thuộc:
    • cùng cột (j),
    • cột trái (j - 1),
    • cột phải (j + 1) (nếu hợp lệ).
  • Hai con không được ở cùng một ô trong cùng một thời điểm.
  • Khi đi qua một ô, Thạch Sùng ăn hết muỗi ở ô đó.
🧮 Kỹ thuật sử dụng: Quy hoạch động 3 chiều (DP)
💡 Định nghĩa trạng thái:

dp[i][j1][j2] là số muỗi tối đa có thể ăn được nếu:

  • đang ở hàng i,
  • con Thạch Sùng thứ nhất ở cột j1,
  • con Thạch Sùng thứ hai ở cột j2.

Lưu ý: j1 ≠ j2

🔁 Quy hoạch động:
Khởi tạo:
for (j1 = 0..n-1)
  for (j2 = 0..n-1)
    if (j1 != j2)
      dp[0][j1][j2] = a[0][j1] + a[0][j2];
Chuyển trạng thái:

Với mỗi hàng i từ 1 đến m-1, cập nhật từ hàng trên:

for (dj1 in {-1, 0, 1})
  for (dj2 in {-1, 0, 1})
    pj1 = j1 - dj1;
    pj2 = j2 - dj2;
    if (pj1, pj2 hợp lệ và pj1 ≠ pj2)
      dp[i][j1][j2] = max(dp[i][j1][j2], dp[i-1][pj1][pj2] + a[i][j1] + a[i][j2]);
✅ Kết quả:

Giá trị lớn nhất ở hàng cuối cùng:

ans = max(dp[m-1][j1][j2]) for all j1 ≠ j2
⏱️ Độ phức tạp:
  • Thời gian: O(m * n^2 * 9) với m, n ≤ 100 ⇒ chạy tốt trong giới hạn.
  • Bộ nhớ: O(m * n^2).
#include <bits/stdc++.h>
using namespace std;

const int INF = -1e9;

int main() {
    int m, n;
    cin >> m >> n;

    vector<vector<int>> a(m, vector<int>(n));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> a[i][j];

    // dp[i][j1][j2] = max muỗi ăn được khi ở hàng i, cột j1 và j2
    vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(n, INF)));

    // Khởi tạo cho hàng đầu tiên
    for (int j1 = 0; j1 < n; ++j1) {
        for (int j2 = 0; j2 < n; ++j2) {
            if (j1 != j2)
                dp[0][j1][j2] = a[0][j1] + a[0][j2];
        }
    }

    // Các bước đi có thể theo chiều ngang: trái (-1), đứng yên (0), phải (+1)
    int dir[] = {-1, 0, 1};

    for (int i = 1; i < m; ++i) {
        for (int j1 = 0; j1 < n; ++j1) {
            for (int j2 = 0; j2 < n; ++j2) {
                if (j1 == j2) continue; // 2 con không được ở cùng 1 ô

                int best = INF;
                for (int dj1 : dir) {
                    for (int dj2 : dir) {
                        int pj1 = j1 - dj1;
                        int pj2 = j2 - dj2;
                        if (pj1 >= 0 && pj1 < n && pj2 >= 0 && pj2 < n && pj1 != pj2) {
                            best = max(best, dp[i-1][pj1][pj2]);
                        }
                    }
                }

                if (best != INF)
                    dp[i][j1][j2] = best + a[i][j1] + a[i][j2];
            }
        }
    }

    // Tìm kết quả lớn nhất ở hàng cuối cùng
    int ans = 0;
    for (int j1 = 0; j1 < n; ++j1) {
        for (int j2 = 0; j2 < n; ++j2) {
            if (j1 != j2)
                ans = max(ans, dp[m-1][j1][j2]);
        }
    }

    cout << ans << endl;
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.