Hướng giải của VOI 14 Bài 2 - Dãy con chung bội hai dài nhất

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.

🔮 Giải thuật "Dãy con chung bội hai dài nhất" (LCS2X)

📅 Mô tả bài toán:

Cho \(2\) dãy \(A\) (kích thước \(m\)) và \(B\) (kích thước \(n\)), tìm dãy con \(C\) sao cho:

  • \(C\) là dãy con của \(A\) và \(B\) (giữ nguyên thứ tự)
  • Thỏa mãn ràng buộc: 2 * c_i <= c_{i+1}
  • Mục tiêu: Tìm dãy con C dài nhất

🚀 Ý tưởng chi tiết:

Bước \(1\): Nén giá trị
  • Dòng \(A\) và \(B\) có thể chứa giá trị rất lớn (lên đến \(10^9\))
  • Ta gom tất cả giá trị của \(A\) và \(B\) lại rồi nén chỉ số thông qua lower_bound
Bước \(2\): Đếm số lượng số \(0\)
  • Trước mỗi vị trí i trong \(A\), gọi ca[i] = số lượng số 0 đứng trước
  • Tương tự cho \(B\): cb[j]
  • Số \(0\) luôn thỏa ràng buộc 2*0 <= x, nên ta có thể gắn tự do bao nhiêu số \(0\) vào dãy con
Bước \(3\): Tiền xử mảng nextb[][]
  • nextb[i][val] = vị trí trong \(B\) (bắt đầu từ \(i\)) gặp giá trị = val
  • Giúp kiểm tra nhanh xem \(b[i..n]\) có chứa a[j] hay không, dùng trong DP
Bước \(4\): Quy hoạch động theo chiều sâu dãy con
  • f[i][h]: trong \(A\), dãy con dài h bắt đầu từ a[i] có thể kết thúc ở vị trí nào trong \(B\)
  • Khởi tạo:
    • h = 1: tìm \(b[j] == a[i]\) trong \(B\) → gán f[i][1] = nextb[n][a[i]]
  • Tính f[i][h] với \(h > 1\):
    • Duyệt i > i, nếu c[a[i]] * 2 <= c[a[ii]] (thỏa điều kiện)
    • Dùng f[i][h-1] (vị trí trong \(B\) của dãy trước) để xem có gắn được a[i] vào trước hay không
Bước \(5\): Cập nhật kết quả
  • Nếu f[i][h] != 0 (tồn tại dãy con dài h bắt đầu từ a[i])
  • Cập nhật:
    res = max(res, h + min(ca[i - 1], cb[f[i][h] - 1]));
    • Thêm số lượng số \(0\) có thể ghép vào trước

🔄 Độ phức tạp:

  • Nén giá trị: O((m+n) log(m+n))
  • DP: O(m * h * m) với h ≤ 31 → chấp nhận được
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3011;

int a[MAXN], b[MAXN], m, n; // Dãy A và B, độ dài m và n
int c[MAXN * 2], s;         // Mảng dùng để nén giá trị
int nextb[MAXN][MAXN];      // nextb[i][v]: vị trí đầu tiên ≥ i trong B có giá trị v
int ca[MAXN], cb[MAXN];     // ca[i], cb[i]: số lượng số 0 trong A, B từ 1 đến i
int f[MAXN][55];            // f[i][h]: vị trí trong B kết thúc nếu dãy con độ dài h bắt đầu tại A[i]

void init() {
    // Đếm số lượng số 0 trước mỗi vị trí
    ca[0] = cb[0] = 0;
    for (int i = 1; i <= m; ++i) ca[i] = ca[i - 1] + (a[i] == 0);
    for (int i = 1; i <= n; ++i) cb[i] = cb[i - 1] + (b[i] == 0);

    // Nén giá trị để xử lý giá trị lớn
    s = 0;
    for (int i = 1; i <= m; ++i) c[++s] = a[i];
    for (int i = 1; i <= n; ++i) c[++s] = b[i];
    sort(c + 1, c + s + 1);
    s = unique(c + 1, c + s + 1) - c - 1;

    for (int i = 1; i <= m; ++i)
        a[i] = lower_bound(c + 1, c + s + 1, a[i]) - c;

    for (int i = 1; i <= n; ++i)
        b[i] = lower_bound(c + 1, c + s + 1, b[i]) - c;

    // Khởi tạo bảng nextb
    // nextb[i][v]: vị trí đầu tiên ≥ i trong B có giá trị v
    memset(nextb, 0, sizeof nextb);
    for (int i = n; i >= 1; --i) {
        for (int j = 1; j <= i; ++j) {
            nextb[i][b[j]] = j;
        }
    }
}

void solve() {
    int res = min(ca[m], cb[n]); // Bắt đầu với số 0 tối đa có thể gắn đầu

    memset(f, 0, sizeof f);

    // Duyệt ngược A từ cuối về đầu
    for (int i = m; i >= 1; --i) {
        for (int h = 1; h <= 31; ++h) {
            if (c[a[i]] == 0) continue; // Bỏ qua nếu a[i] là số 0 đã bị nén

            if (h == 1) {
                // Dãy con độ dài 1 → cần b[j] == a[i] ở bất kỳ đâu trong B
                f[i][1] = nextb[n][a[i]];
            } else {
                f[i][h] = 0;
                if (f[i][h - 1] == 0) continue; // Nếu không có dãy độ dài h-1 thì bỏ qua

                // Tìm phần tử ii sau i trong A sao cho a[i] * 2 ≤ a[ii]
                for (int ii = i + 1; ii <= m; ++ii) {
                    if (c[a[i]] * 2 <= c[a[ii]]) {
                        int u = f[ii][h - 1]; // Vị trí trong B kết thúc dãy độ dài h-1
                        f[i][h] = max(f[i][h], nextb[u][a[i]]);
                    }
                }
            }

            // Nếu tồn tại dãy con độ dài h bắt đầu từ i
            if (f[i][h]) {
                // Cộng thêm số 0 có thể chèn vào đầu từ A và B
                int zeros = min(ca[i - 1], cb[f[i][h] - 1]);
                res = max(res, h + zeros);
            }
        }
    }

    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        cin >> m >> n;
        for (int i = 1; i <= m; ++i) cin >> a[i];
        for (int i = 1; i <= n; ++i) cin >> b[i];

        init();
        solve();
    }
    return 0;
}

Nhận xét

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