# dp1 solution
==**DP LIS, LIQ**==
## dp1 - LIQ - Dãy con tăng không ngặt dài nhất
Gọi $DP[i]$ là độ dài dãy con tăng dài nhất tới vị trí $i$ và bao gồm cả $i$.

Ta có nhận xét:
$\rightarrow$ Phần tử thứ $i$ có thể được gắn ở cuối dãy con tăng kết thúc tại $j$ nếu $A_j \le A_i$.

Do đó: $DP[i] = max(DP[j] + 1)$ với mọi $j < i$ và $A_j \le A_i$

Đáp án là $max(DP[i])$

ĐPT $O(n^2)$

### Code

#include<bits/stdc++.h>
using namespace std;

long long DP[10000001];
long long arr[10000001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    freopen("liq.inp", "r", stdin);
    freopen("liq.out", "w", stdout);
    int n;
    cin >> n;
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        DP[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (arr[j] <= arr[i]) 
            {
                DP[i] = max(DP[i], DP[j] + 1);
            }
        }
        ans = max(ans, DP[i]);
    }
    cout << ans;
    return 0;
}

## dp1 - LIS - Dãy con tăng ngặt dài nhất

Bài này có giới hạn $N$ lên tới $10^5$ nên ta sẽ sử dụng kỹ thuật mới để xây dựng dãy con tăng tối ưu.

Ta sẽ xây dựng một dãy con tăng tối ưu trong quá trình duyệt qua các phần tử từ $A_1 \rightarrow A_n$.

Dãy con tăng được gọi là tối ưu nhất khi độ dài nó là lớn nhất, và mỗi giá trị mỗi phần tử là nhỏ nhất.

Gọi mảng $f$ là mảng chứa dãy con tăng tối ưu.

Khi xét một phần tử $A_i$ bất kì, $A_i$ sẽ tối ưu cho vị trí j mà $f[j] \ge A_i$ và $f[j - 1] < A_i$. Ta có thể tìm vị trí $j$ bằng cách chặt nhị phân hoặc sử dụng hàm lower_bound có sẵn của C++.

Nếu tồn tại vị trí $j$ thì $f[j] = A_i$.
Ngược lại thì ta thêm $A_i$ vào cuối dãy con tăng mảng $f$.

Kỹ thuật này nghiên về tham lam hơn là quy hoạch động.

Đáp án sẽ độ dài của $f$ sau khi duyệt qua tất cả phần tử.

ĐPT $O(N \times logN)$

### Code

#include<bits/stdc++.h>
using namespace std;

int A[100001];
int f[100001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    freopen("LIS.inp", "r", stdin);
    freopen("LIS.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> A[i];
    int m = 0;
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; i++) {
        int j = lower_bound(f + 1, f + 1 + m, A[i]) - f;
        if (j > m) m++;
        f[j] = A[i];
    }
    cout << m;
    return 0;
}

## dp1 - TOWER - Tòa tháp

Nếu gọi $DP[i]$ là độ cao cao nhất của tòa tháp có khối trụ trên cùng là khối trụ thứ $i$.

Ta có nhận xét:
$\rightarrow$ Khối trụ thứ $i$ có thể được gắn ở đầu tháp có khối trụ trên cùng là $j$ nếu $R_j \le R_i$.

$\rightarrow DP[i] = max(DP[j] + H[i])$ với mọi $j < i$ và $R_j \le R_i$.

Song cách này có ĐPT là $O(N^2)$ nếu ta duyệt thông thường.

Nhận thấy rằng khi tìm vị trí $j$ tối ưu, ta chỉ cần quan tâm $R_j$ và độ cao tháp tại đó.

Do đó ta sẽ thay đổi mảng $DP$ như sau:

Gọi $DP[i]$ là độ cao cao nhất của tòa tháp có khối trụ trên cùng bán kính là $i$.

Khi duyệt phần tử thứ $i$:
$\rightarrow DP[R_i] = max(DP[j] + H[i])$ với mọi $j \le R_i$.

Đáp án là $max(DP[R_i])$.

ĐPT: $O(N * max(R_i))$.

>[!Note]
>tối đa $O(N * 500)$ do $R_i \le 500$

### Code

#include<bits/stdc++.h>
using namespace std;

int DP[501];
int R[100001];
int H[100001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    freopen("tower.inp", "r", stdin);
    freopen("tower.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> R[i] >> H[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = R[i]; j <= 500; j++)
        {
            DP[R[i]] = max(DP[R[i]], DP[j] + H[i]);
        }
        ans = max(ans, DP[R[i]]);
    }
    cout << ans;
    return 0;
}

## dp1 - STADIUM - Thuê sân bóng
Gọi $DP[i]$ là tổng số tiền thuê được nhiều nhất khi đội bóng $i$ là đội bóng thuê cuối cùng

Nhận thấy rằng, nếu đội bóng $j$ được thuê trước đội bóng $i$ thì $a_j \le b_j \le a_i \le b_i$

Do đó nếu đặt mảng $DP$ như trên, ta cần sắp xếp các đội tăng dần theo $b$ có nghĩa là tăng dần theo thời gian kết thúc thuê.

Việc sắp xếp để đảm bảo rằng, khi ta xét với đội bóng $i$ thì mọi đội bóng $j$ mà $b_j \le a_i$ đều được duyệt trước đó.

Ta sẽ có công thức:

$DP[i] = max(DP[j] + c_i)$ với mọi $j < i$ và $b_j \le a_i$

### Code

#include<bits/stdc++.h>
#define int long long
using namespace std;

struct ntype {
    int s, e, c;
};

bool cmp(const ntype& a, const ntype& b) {
    return a.e < b.e;
}

ntype arr[5001];
int DP[5001];

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    freopen("STADIUM.inp", "r", stdin);
    freopen("STADIUM.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].s >> arr[i].e >> arr[i].c;
    }
    sort(arr + 1, arr + 1 + n, cmp);
    arr[0].e = -1;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j].e <= arr[i].s) {
                DP[i] = max(DP[i], DP[j] + arr[i].c);
            }
        }
        ans = max(ans, DP[i]);
    }
    cout << ans;
    return 0;
}

## dp1 - EXP - Biểu thức số học

Thấy rằng:
* Mỗi phần tử có hai sự lựa chọn là cộng hoặc trừ.
* Việc quyết định dấu cho mỗi phần tử là độc lập với nhau - có nghĩa là không yêu cầu về số lượng, thứ tự các phần tử được cộng hoặc trừ.
* Gọi $K$ là tổng sau cùng sau khi đặt dấu $N$ số $\rightarrow -25000 \le K \le 25000$

Gọi $DP[i][j]$ là trạng thái của tổng $j$ khi đã đặt dấu $i$ phần tử đầu tiên, ta có:

* $DP[i][j] = true$ có nghĩa là tồn tại cách đặt dấu cho $i$ phần tử đầu tiên để được tổng $j$.
* $DP[i][j] = false$ thì ngược lại.

Với $i = 1: DP[1][A_1] = true$
>do phần tử đầu tiên chỉ có thể đặt dấu cộng.

Với $i > 1: DP[i][j] = true$ khi và chỉ khi:

* $j - A_i \ge -25000$ và $DP[i - 1][j - A_1] = true$

hoặc

* $j + A_i \le 25000$ và $DP[i - 1][j + A_1] = true$

Vì $j$ có thể $< 0$ nên ta cần cộng thêm hằng số sao cho $j$ luôn $\ge 0$.

Do đó $DP[N][S] = true$ thì in ra $YES$

Trường hợp ngược lại in ra $NO$

ĐPT: $O(N \times 50000)$

### Code

#include<bits/stdc++.h>
using namespace std;

int arr[100001];
bool DP[501][50001];

// ta đặt hằng số b để mảng DP ko âm
const int b = 25000;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    freopen("exp.inp", "r", stdin);
    freopen("exp.out", "w", stdout);
    int n, s;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    cin >> s;
    DP[1][arr[1] + b] = true;
    for (int i = 2; i <= n; i++)
    {
        for (int j = -25000; j <= 25000; j++)
        {
            if (j - arr[i] >= -25000 && DP[i - 1][j - arr[i] + b])
                DP[i][j + b] = true;
            if (j + arr[i] <= 25000 && DP[i - 1][j + arr[i] + b]) 
                DP[i][j + b] = true;
        }
    }
    if (DP[n][s + b]) cout << "YES";
    else cout << "NO";
    return 0;
}

## dp1 - SPSEQ - Dãy dài đẹp nhất
Gọi:

* $DP[i]$ là dãy con tăng dài nhất từ 1 đến $i$, và dãy bao gồm cả $i$.
* $DP2[i]$ là dãy con giảm dài nhất từ $i$ đến $N$ và dãy bao gồm cả $i$.

Do đó, nếu $i$ là trung điểm của dãy đẹp (có nghĩa là vị trí ở giữa và có giá trị cao nhất) thì độ dài dài nhất của dãy đẹp là:

==$\large \min(DP1[i], DP2[i]) \times 2 - 1$==

Vì vậy ta chỉ cần tính $DP[i]$ và $DP2[i]$ với mọi $i$, sau đó tìm vị trí trung điểm sao cho dãy đẹp dài nhất.

Cách tính $DP$ và $DP2$ tương tự như bài LIS trước đó

ĐPT $O(N \times logN)$

### Code

#include<bits/stdc++.h>
using namespace std;

int DP1[100001];
int DP2[100001];
int arr[100001];
int lb[100001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    freopen("SPSEQ.inp", "r", stdin);
    freopen("SPSEQ.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];

    int ma = 0;
    memset(lb, 0x3f, sizeof lb);
    for (int i = 1; i <= n; i++)
    {
        int p = lower_bound(lb + 1, lb + 1 + ma, arr[i]) - lb;
        if (p > ma) ma++;
        lb[p] = arr[i];
        DP1[i] = ma;
    }
    ma = 0;
    memset(lb, 0x3f, sizeof lb);
    for (int i = n; i >= 1; i--)
    {
        int p = lower_bound(lb + 1, lb + 1 + ma, arr[i]) - lb;
        if (p > ma) ma++;
        lb[p] = arr[i];
        DP2[i] = ma;
    }
    int ans = 1;
    for (int i = 1; i <= n; i++) 
    {
        ans = max(ans, min(DP1[i], DP2[i]) * 2 - 1);
    }
    cout << ans;
    return 0;
}

## dp1 - BEADS - Vỏ ốc nhiều nhất
Đây gần như là bài DP khó nhất trong dp1

Do ta xét lần lượt các vỏ ốc từ trái sang phải, nên khi xét tới vỏ ốc thứ $i$, ta có 3 lựa chọn sau:

1. Thêm $A_i$ vào bên trái dãy con tăng.
2. Thêm $A_i$ vào bên phải dãy con tăng.
3. Bỏ $A_i$.

Với $N \le 10^5$, ta không thể lưu được quá nhiều thông tin về dãy con tăng trước đó, việc lựa chọn cách tối ưu với $A_i$ là gần như không thể.

Tuy nhiên, nếu ta xác định một vị trí $k < i$, và ta biết $A_k$ nằm trong dãy con tăng thì ta sẽ lượt bớt còn 2 lựa chọn:

1. Thêm $A_i$ vào bên trái dãy con tăng nếu $A_i < A_k$ hoặc vào bên phải dãy con tăng nếu $A_i > A_k$.
2. Bỏ $A_i$.

Vì vậy, nếu xác định được trước vị trí $k$, thì mỗi phần tử $i > k$,

Gọi:
* $DP1[i]$ là dãy con **tăng** dài nhất từ $i \rightarrow N$ và bao gồm cả $A_i$
* $DP2[i]$ là dãy con **giảm** dài nhất từ $i \rightarrow N$ và bao gồm cả $A_i$

Với mỗi vị trí $k$, nếu ta xét $A_k$ là phần tử đầu tiên được đưa vào dãy con tăng thì dãy con tăng có độ dài dài nhất là $DP1[k] + DP2[k] - 1$

Do đó đáp án sẽ là $\max(DP1[i] + DP2[i] - 1)$ với mọi $i$

ĐPT $O(N \times logN)$

### Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

int arr[1000001];
int DP1[1000001], DP2[1000001];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    freopen("BEADS.inp", "r", stdin);
    freopen("BEADS.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    reverse(arr + 1, arr + 1 + n);
    int m1 = 0, m2 = 0;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int p1 = lower_bound(DP1, DP1 + m1, arr[i]) - DP1;
        DP1[p1] = arr[i];
        if (m1 < p1 + 1) m1++;
        int p2 = lower_bound(DP2, DP2 + m2, -arr[i]) - DP2;
        DP2[p2] = -arr[i];
        if (m2 < p2 + 1) m2++;
        ans = max(p1 + p2 + 1, ans);
    }
    cout << ans;
    return 0;
}

## dp1 - STICK - Thời gian ít nhất
Bài này không phải DP mà là một bài toán tham lam điển hình.

Giả sử các phần tử sắp xếp theo $L_i$, nếu $L_a = L_b$ thì ta sắp xếp theo $W$, cả 2 đều tăng dần.

Khi ta xét phần tử thứ $i$, ta sẽ các lựa chọn chia làm 2 dạng:

1. Đưa nó vào tập hợp các đoạn gỗ mà đoạn gỗ cuối cùng là đoạn gỗ thứ $j$ với $W_j \le W_i$ và $j < i$, việc này sẽ có chi phí là $0$.

2. Để đoạn gỗ thứ $i$ là đoạn gỗ đầu tiên của một tập hợp các đoạn gỗ tăng dần mới, việc này sẽ có chi phí là $1$.

Xét thao tác thứ nhất, thì trong mọi trường hợp, đều tạo ra tập hợp đoạn gỗ mới có đoạn gỗ cuối cùng trọng lượng là $W_i$. Do đó, để tối ưu nhất ta sẽ chọn $j$ sao cho $W_j$ là lớn nhất và vẫn thỏa mãn.

Vì chi phí ở thao tác thứ nhất luôn là $1$, nên nếu ta sắp xếp theo $L$ như trên thì khi ta xét từng phần tử từ trái qua phải sẽ tối ưu nhất.

ĐPT: $O(N \times logN)$

1 bài tương tự, có cùng cách làm, các bạn có thể dùng để luyện tập https://cses.fi/problemset/task/1632

### Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

pair<int, int> arr[5001];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    freopen("STICK.inp", "r", stdin);
    freopen("STICK.out", "w", stdout);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> arr[i].first >> arr[i].second;
        }
        multiset<int> ms;
        sort(arr + 1, arr + 1 + n);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (ms.lower_bound(-arr[i].second) != ms.end()) {
                ms.erase(ms.lower_bound(-arr[i].second));
            }
            else ans++;
            ms.insert(-arr[i].second);
        }
        cout << ans << '\n';
    }
    return 0;
}

## dp1 - NEMCHUA - Nem chua

Nhận thấy rằng: việc chia nhóm không cần các phần tử nằm liên tiếp, mỗi phần tử có thể tham gia một nhóm bất kì, chi phí cho một nhóm là: $max$ trong nhóm - $min$ trong nhóm.

Do đó, nếu ta sắp xếp các phần tử từ bé đến lớn, thì cách chia nhóm tối ưu nhất sẽ là chia nhóm gồm phần tử nằm liên tiếp.

Vì đã sắp xếp, $max$ trong nhóm sẽ nằm bên phải cùng và $min$ nằm bên trái cùng.

Vd: $N = 8, M = 4$


Nếu ta chia thành $M$ nhóm sẽ có $M + 1$ vách ngăn, vách ngăn thứ $1$ và thứ $M + 1$ sẽ nằm vị trí cố định là đầu và cuối.

$M - 1$ vách ngăn còn lại, mỗi vách ngăn sẽ có dạng $l_{i, i + 1}$ ngăn cách phần tử $i$ và $i + 1$.

Bài toán sẽ là ta tìm cách đặt $M - 1$ vách ngăn đó sao cho tổng chi phí là thấp nhất, nhận thấy: vách ngăn $l_{i, i + 1}$ sẽ có chi phí là $a_i - a_{i + 1}$ (như hình).

Do đó, ta chỉ cần tính chi phí để đặt mỗi vách ngăn, sau đó tìm $M - 1$ vách ngăn chi phí bé nhất.

Đáp án sẽ là $a_n - a_1 \space +$ ***<tổng chi phí $M - 1$ vách ngăn tối ưu>***

ĐPT: $O(N \times logN)$

### Code

#include <bits/stdc++.h>
using namespace std;

int arr[201];
int dif[201];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    freopen("NEMCHUA.inp", "r", stdin);
    freopen("NEMCHUA.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    sort(arr + 1, arr + 1 + n);
    for (int i = 1; i < n; i++) dif[i] = arr[i] - arr[i + 1];
    sort(dif + 1, dif + n);
    int ans = 0;
    for (int i = 1; i < min(n, m); i++) ans += dif[i];
    cout << ans - arr[1] + arr[n];
    return 0;
}