\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hướng dẫn}}\)

• Xét đến vị trí thứ \(i\) của mảng \(a[]\), vị trí thứ \(j\) của mảng \(b[]\), và đã chọn \(c\) cặp trước đó. Hỏi tổng lón nhất kể từ đây hoặc đến đay là bao nhiêu

\(\color{goldenrod}{\text{Tiếp cận}}\)

• Xét mảng quy hoạch động \(f[i][j][c]\) hoặc hàm đệ quy có nhớ \(f(i, j, c)\)

Nếu \(c = k\) thì mình đã chọn đúng, nên \(f(i, j, c) = 0\)

Nếu \(c > k\) thì minh đã chọn quá, nên để cho tiện thì \(f(i, j, c) = -\infty\)

Ngược lại có \(c < k\), mà nếu \(i > n\) hay \(j > n\) thì chọn thiếu, nên \(f(i, j, c) = -\infty\)

Nếu không bắt cặp bất cứ ông nào thuộc \(b[]\) với \(a_i\) thì \(V_A = f(i + 1, j, c)\)

Nếu không bắt cặp bất cứ ông nào thuộc \(a[]\) với \(b_j\) thì \(V_B = f(i, j + 1, c)\)

Ngược lại, nếu như tại đây bắt cặp \(a_i\) với \(a_j\) vào \(S\) thì \(V_C = f(i + 1, j + 1, c + 1) + a_i \times b_j\)

Vì ta lấy muốn lấy \(max(S)\) nên \(f(i, j, c) = max(V_A, V_B, V_C)\)

• Tối ưu không gian: Thay vì đệ quy có nhớ, khi thực hiện quy hoạch động bằng vòng lặp có thể giảm chiều \(O(i) \rightarrow O(2)\) hoặc \(O(j) \rightarrow O(2)\)

\(\color{purple}{\text{Độ phức tạp}}\)

• Số trạng thái: \(O(f(x)) = O(O(i) \times O(j) \times O(c)) = O(n \times n \times k) = O(n^2 \times k)\)

• Chi phí chuyển trạng thái: \(O(4) = O(1)\)

\(\color{green}{\text{Code tham khảo }}\): Quy hoạch động

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n^2 \times k)\ \color{purple}{\text{thời gian}}\ ||\ O(n^2 \times k)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;
const int LIM = 1e3 + 13;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int n, k;
int a[LIM];
int b[LIM];
ll f[LIM][LIM][6];

ll solve(int i = 1, int j = 1, int c = 0)
{
    if (c == k) return 0;
    if (i > n || j > n) return -LINF;

    ll &res = f[i][j][c];
    if (res != -1) return res;

    res = max(solve(i + 1, j, c), solve(i, j + 1, c));
    res = max(res, solve(i + 1, j + 1, c + 1) + 1LL * a[i] * b[j]);
    return res;
}

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];

    memset(f, -1, sizeof(f));
    cout << solve();
    return 0;
}