\(\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}}\)

• Ta quy về bài toán quy hoạch động, xét xem đoạn \((l, r)\) tối đa chia được cho bao nhiêu bạn học sinh

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

• Gọi \(f(l, r)\) là số lượng học sinh tối đa được chia quà từ đoạn \((l, r)\)

Ban đầu gọi tới \(f(1, 2 \times n)\) tức là mọi món quà đều có thể chia cho học sinh

Khi \(l = r\) thì \(f(l, r) = 0\) vì không thể chia cho học sinh chỉ một món quà

Khi \(l > r\) thì \(f(l, r) = 0\) bởi vì không còn quà đề chia học sinh

• Xét các trường hợp

Thử lấy cặp giá trị \((c[l], c[r])\), bạn học sinh thứ \(k\) nào đó sẽ nhận \(c[l]\) vào lượt đầu và \(c[r]\) vào lượt sau, tức là chỉ được lấy khi \(| c[l] - c[r] | \leq d\)

Thử không lấy giá trị \(a[l]\) và xét đoạn \((l + 1, r)\)

Thử không lấy giá trị \(a[r]\) và xét đoạn \((l, r - 1)\)

Kết quả của hàm quy hoạch động là \(f(l, r)\) bằng giá trị lớn nhất của 3 cách trên

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

• Số trạng thái của quy hoạch động là \(O(n^2)\) (Vì \(1 \leq l \leq r \leq 2 \times n\))

• Chi phí chuyển trạng thái là \(O(1)\) (xét cùng lắm có 3 trường hợp)

• Vậy độ phức tạp thuật toán là \(O(n^2)\)

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

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

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 2 * 2020;

int n, d;
int c[LIM];
int f[LIM][LIM];
int solve(int l = 1, int r = 2 * n)
{
    if (l >= r) return 0;
    int &res = f[l][r];
    if (res != -1) return res;

    if (abs(c[l] - c[r]) <= d)
        return res = solve(l + 1, r - 1) + 1;

    return res = max(solve(l + 1, r), solve(l, r - 1));
}

int main()
{
    cin >> n >> d;
    for (int i = 1; i <= 2 * n; ++i)
        cin >> c[i];

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