let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

VOI 2014 LCS2X - Dãy con chung bội 2 dài nhất

solution.md

Gọi \(f(i, j)\) là dãy con chung bội 2 dài nhất kết thúc ở \(a_i\) và \(b_j\).

Ta có công thức tính \(f(i, j)\) như sau:

  • \(f(i, j) = 0\) khi \(a_i \neq b_j\)
  • Ngược lại, ta có \(f(i, j) = max\{f(k, l) \mid k < i \land l < j \land 2\times a_k \leq a_l\} + 1\).

Ta có thể dễ dàng tính \(f\) trong \(O(m^2 n^2)\). Tuy nhiên, để AC cần cải tiến về \(O(n^2)\).

Trong đoạn code trên, \(y\) là mảng QHĐ, còn \(x\) là mảng mảng dùng để tìm max.

main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int m, n; cin >> m >> n;
        vector<int> a(m), b(n);
        for (int &a: a) cin >> a;
        for (int &b: b) cin >> b;
        vector<int> x(m, 0), y(n, 0);
        int res = 0;
        for (int i=0; i<m; i++) for (int j=0; j<n; j++) {
            int tmp = x[i];
            if (b[j]*2 <= a[i]) x[i] = max(x[i], y[j]);
            if (a[i] == b[j]) {
                y[j] = tmp + 1;
                res = max(res, y[j]);
            }
        }
        cout << res << '\n';
    }
    return 0;
}
Comments