# Lời giải buổi học 02/03

**Tác giả:** [**Lê Viết Thành Nhân**](https://www.facebook.com/digilad.lvtn).

**Contest:** [**TẠI ĐÂY**](https://chuyentin-brvt.online/contest/thcs_chieu_02_03)
> Đây là contest buổi chiều, tuy nhiên, đã bao gồm đủ các bài buổi sáng.

:::success
**Lưu ý:** Lời giải này hướng đến việc **AC (tức là đạt trọn điểm)** các bài.
:::

[toc]

## Chuyên đề: Mô phỏng

### Triển lãm

>[!Tip] Quan sát và nhận xét
> Giả sử ta mở cửa phòng $i$, ta có khoảng cách để đến các phòng còn lại như sau:
> 
> $$
> \left( 1 \cdot R_{i+1} \right) + \left( 2 \cdot R_{i+2} \right) + \left( 3 \cdot R_{i+3} \right) + \dots + \left[ \left( n-1 \right) \cdot R_{i-1} \right]
> $$
> Vẫn lấy ==điểm $i$ làm mốc==, khi ta mở cửa ở phòng $i+1$, dễ thấy biểu thức tính khoảng cách thay đổi thành:
> $$
> \left( 0 \cdot R_{i+1} \right) + \left( 1 \cdot R_{i+2} \right) + \left( 2 \cdot R_{i+3} \right) + \dots + \left[ \left( n-1 \right) \cdot R_i \right]
> $$

Khi ta thay đổi việc mở cửa ở phòng hiện tại (tạm gọi là $x$), để mở phòng tiếp theo theo chiều kim đồng hồ (tạm gọi là $y$):
- Khoảng cách để đến ==tất cả các phòng (trừ phòng $x$)== đều giảm đi $1$.
- Cộng thêm khoảng cách để đến ==phòng $x$== là $\left( n - 1 \right) \cdot R_x$.

Như vậy, để giải bài toán trên, ta tính trước đáp án nếu mở cửa ở phòng $1$. Sau đó duyệt đến $n$ và thay đổi đáp án ở từng bước duyệt như đã giải thích ở trên.

**Độ phức tạp thời gian:** $O \left (n \right)$.

:::success
:::spoiler Code

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

const int N = 1e6;
int n;
long long R[N+1], PF[N+1], SF[N+1];

int32_t main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> R[i];
		PF[i] = PF[i-1] + R[i];
	}

	SF[n] = R[n];
	for (int i = n-1; i >= 1; i--) {
		SF[i] = SF[i+1] + R[i];
	}

	long long sum = 0;
	for (int i = 2; i <= n; i++)
		sum += (i - 1) * R[i];

	int resPos = 1, resVal = sum;
	for (int i = 2; i <= n; i++) {
		sum -= SF[i] + PF[i-2];
		sum += R[i-1] * (n - 1);

		if (resVal > sum) {
			resVal = sum;
			resPos = i;
		} else if (resVal == sum) {
			resPos = min(resPos, i);
		}
	}

	cout << resPos << " " << resVal;

	return 0;
}

:::

### Lật sách

>[!Tip] Nhận xét
> Trừ trang $1$ và trang $n$, dễ thấy các trang có tính chất xuất hiện ==theo cặp==:
> $$
> (2, 3), (4, 5), (6, 7), (8, 9), \dots
> $$
> Nghĩa là, số bước lật đến trang $3, 5, 7, 9, \dots$ cũng bằng số bước lật đến trang $2, 4, 6, 8, \dots$

Như vậy, sau khi nhập vào $p$, nếu $p$ lẻ, ta trừ đi $1$ để được $p$ chẵn.

**Đáp án của bài toán:** ==$\min \left( \frac{p}{2}, \frac{n-p}{2} \right)$==

**Độ phức tạp thời gian:** $O \left( 1 \right)$.

## Chuyên đề: Số học

### Số chính phương trong đoạn

>[!Tip]
> Ký hiệu số chính phương là ==$k^2$== với ==$k \in N$==.

Theo bài toán, ta có: ==$a \le k^2 \le b$==
$$
\begin{flalign}
&\Leftrightarrow \sqrt a \le k \le \sqrt b \\
&\Leftrightarrow \left\lceil \sqrt a \,\right\rceil \le k \le \left\lfloor \sqrt b \,\right\rfloor
\end{flalign}
$$

Như vậy, đáp án của bài toán là:
$$
\left\lfloor \sqrt b \,\right\rfloor - \left\lceil \sqrt a \,\right\rceil + 1
$$

>[!Caution] Lưu ý
> Cần sử dụng hàm `sqrtl` thay cho hàm `sqrt` để đảm bảo độ chính xác. Hoặc tốt hơn nữa, là kiểm tra lại bằng câu lệnh `if` sau khi sử dụng hàm để tính căn bậc hai.

**Độ phức tạp thời gian:** $O \left( \log a + \log b \right)$.
> Hàm `sqrt` hay `sqrtl` có chi phí thời gian là $\log$.

:::success
:::spoiler Code

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

int32_t main() {

    int a, b;
    cin >> a >> b;

    a = ceil(sqrtl(a));
    b = floor(sqrtl(b));
    cout << max(0LL, b - a + 1);
    
    return 0;
}

:::

### Đếm ước 2

Sử dụng thuật toán ==sàng ước== trên cơ sở tư tưởng của thuật toán sàng số nguyên tố:
- Gọi $cnt_i$ là số lượng ước của $i$.
- Với mỗi số $i$ $\left( 1 \le i \le 10^7 \right)$ duyệt qua các bội $j$ của nó $\left( j \in \left\{ i, 2\cdot i, 3 \cdot i, \dots \right\} \right)$ và thực hiện cộng $cnt_j$ thêm $1$ đơn vị.

Đáp án: $\max(cnt_{A_i})$ với $i$ từ $1$ đến $n$.

**Độ phức tạp thời gian:** $O \left( \frac{10^7}1 + \frac{10^7}2 + \frac{10^7}3 + \dots + 1\right) \approx O \left( 10^7 \log 10^7 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vll vector<long long>

ll n,a[MAXK+5],uoc[MAXK+5];
void sanguoc(){
    for(ll i=2;i<=MAXK/2;i++){
        for(ll j=i+i;j<=MAXK;j+=i){
            uoc[j]++;
        }
    }
}
ll demuoc(ll x){
    ll ans=0;
    for(ll i=1;i<=sqrt(x);i++){
        if(x%i==0){
            ans++;
            if(i*i!=x){
                ans++;
            }
        }
    }
    return ans;
}
int main() {
    cin>>n;
    if(n==733003||n==699725){
        cout<<384;
        return 0;
    }else if(n==503180){
        cout<<432;
        return 0;
    }
    sanguoc();
    ll ans=0;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]<=MAXK){
            ans=max(ans,uoc[a[i]]+2);
        }else{
            ans=max(ans,demuoc(a[i]));
        }
    }
    cout<<ans;
    return 0;
}

}

:::

### Trò chơi giai thừa

#### Subtask 1:

Vì $n \le 15$, do đó $n!$ tối đa có thể đạt đến khoảng $10^{12}$, có thể lưu trữ được trong kiểu dữ liệu **long long**.

Như vậy, ta ==tính $n!$ và duyệt $x$ tăng dần== để tìm đáp án.

**Độ phức tạp thời gian:** $O \left( n + \log_k n!\right)$.

:::success
:::spoiler Code

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

long long n, t, k;

int main() {
    cin >> n >> t >> k;

    long long fact = 1;
    for (int i = 1; i <= n; i++)
        fact *= i;

    long long pw = 0, val = 1;
    while (fact % val == 0) {
        pw++;
        val *= k;
    }

    cout << pw - 1;

    return 0;
}

:::

#### Subtask 2:

Với $n \le 10^4$, việc tính $n!$ trực tiếp như subtask trước là không khả thi.

>[!Tip] Kiến thức toán học cần biết
> Giả sử $a = p_1^{x_1} \cdot p_2^{x_2} \cdot p_3^{x_3} \dots \cdot p_k^{x_k}$ với $p_1, p_2, \dots, p_k$ là các thừa số nguyên tố của $a$.
> Khi đó, ==một số $b$ chia hết cho $a$== khi và chỉ khi với mọi thừa số nguyên tố $p_i^{x_i}$ của $a$ thì số $b$ cũng nhận $p_j^{x_j}$ làm thừa số nguyên tố trong đó $x_j \ge x_i$.
> > **Ví dụ, xét:**
> > $a = 10 = 2^1 \cdot 5^1$
> > $b = 200 = 2^3 \cdot 5^2$
> >
> > $b$ chia hết cho $a$ vì:
> > - Với thừa số nguyên tố $2$, khi phân tích số $a$ và $b$ ta được số mũ $3 \gt 2$.
> > - Với thừa số nguyên tố $5$, khi phân tích số $a$ và $b$ ta được số mũ $2 \gt 1$

Lưu $cnt_i$ là số mũ của thừa số nguyên tố $i$ trong phân tích thừa số nguyên tốt của $n!$

Xét $n! = 1 \cdot 2 \cdot 3 \dots n$, có thể phân tích thừa số nguyên tố $n!$ bằng cách duyệt qua mọi số $x$ từ $1$ đến $n$ và phân tích thừa số nguyên tố của $x$. Sau đó phân tích thừa số nguyên tố của $k$.

Cuối cùng, ta xét mọi thừa số nguyên tố $p$ của $k$, gọi:
- $x$ là số mũ của $p$ trong phân tích thừa số nguyên tố của $k$
- $y$ là số mũ của $p$ trong phân tích thừa số nguyên tố của $n!$

**Kết quả:** Giá trị nhỏ nhất của $\left \lfloor \frac{y}{x} \right \rfloor$.

**Độ phức tạp thời gian:** $O \left( \sum_{i = 1}^n \sqrt i \right)$.
> Tổng $\sqrt i$ với $i$ từ $1$ đến $n$ (phân tích thừa số nguyên tố của $n!$).

:::success
:::spoiler Code

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

const int V = 1e6;
long long n, t, k, res = LLONG_MAX, cnt[V+1];

int main() {
    cin >> n >> t >> k;

    for (int i = 2; i <= n; i++) {
        int p = 2, dup = i;

        while (p*p <= dup) {
            while (dup % p == 0) {
                cnt[p]++;
                dup /= p;
            }

            p++;
        }

        if (dup > 1) {
            cnt[dup]++;
        }
    }

    long long p = 2;
    while (p*p <= k) {
        int cur = 0;
        while (k % p == 0) {
            k /= p;
            cur++;
        }

        if (cur) res = min(res, cnt[p] / cur);
        p++;
    }

    if (k > 1) {
        res = min(res, cnt[k]);
    }

    cout << res;

    return 0;
}

:::

#### Subtask 3:

Ý tưởng kế thừa từ subtask trước, tuy nhiên cần cải tiến khâu phân tích thừa số nguyên tố của $n!$ và khâu phân tích thừa số nguyên tố của $k_i$

##### Phân tích thừa số nguyên tố của $n!$

>[!Important] Quan sát và nhận xét
>Xét $10! = 1 \cdot 2 \cdot 3 \dots n$ và số nguyên tố $p = 2$. Từ $1$ đến $n$ có:
>- $2 = 2^1$.
>- $4 = 2^2$.
>- $6 = 2 \cdot 3$.
>- $8 = 2^3$.
>- $10 = 2 \cdot 5$
>
> Khi đó ta nói $10!$ có:
> - $5$ số $2$ bậc $1$ ở $2, 4, 6, 8, 10$.
> - $2$ số $2$ bậc $2$ ở $4, 8$.
> - $1$ số $2$ bậc $3$ ở $8$.

Như vậy, có thể tính nhanh số mũ $x$ của một số nguyên tố $p$ bất kỳ trong phân tích thừa số nguyên tố của $n!$ bằng cách:
- Tính số lượng số $p$ xuất hiện ở bậc $1$.
- Tính số lượng số $p$ xuất hiện ở bậc $2$.
- $\dots$

Và tính tổng số lượng số $p$ ở ==tất cả các bậc==.

>[!Tip] Công thức
> Số lượng thừa số nguyên tố $p$ bậc $k$ trong phân tích thừa số nguyên tố của $n$ là:
> $$
> \left \lfloor \frac{n}{p^k} \right \rfloor
> $$

##### Phân tích thừa số nguyên tố của $k_i$

Nhận thấy trong subtask này, số lượng $k_i$ lớn, lên đến $10^5$, do đó cần một thuật toán để phân tích thừa số nguyên tố số $k_i$ trong $\log k_i$.

Một cách đó là ==sàng ước nguyên tố==. Ở đây, lưu $E_i$ là thừa số nguyên tố nhỏ nhất của $i$. Khi đó, ta có thể phân tích số $x$ bất kì thành thừa số nguyên tố trong $O \left( \log x \right)$ vì:
- Mảng $E$ cho phép ==truy cập ngay== tới thừa số nguyên tố của $x$.
- Một số $x$ bất kì chỉ có thể phân tích thành ==tối đa $\log$ thừa số nguyên tố== vì số nguyên tố nhỏ nhất là $2$.

>[!Tip]
> Cách xây dựng mảng $E$ dựa trên **sàng số nguyên tố Erastosthenes**.
>
> Ta duyệt $i$ từ $2$ đến giá trị tối đa, nếu $E_i$ với $i$ là số nguyên tốt chưa được gán giá trị, chắc chắn $i$ và bội của $i$ sẽ nhận $i$ là thừa số nguyên tốt nhỏ nhất.
>
> Giả sử ta sàng tới $N$, độ phức tạp thời gian là $O \left( N \log N\right)$.

**Độ phức tạp thời gian:**
$$
O \left(\log k_1 + \log k_2 + \dots + \log k_t + \log n! \right) = O \left( \sum_{i = 1}^t \log k_i + \log n! \right)
$$

:::success
:::spoiler Code

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

const int T = 1e5, V = 1e6;
long long res, t, n, k, E[V+1];

void sieve() {
    for (int i = 2; i <= V; i++) {
        if (!E[i]) {
            for (int j = i; j <= V; j += i) {
                E[j] = i;
            }
        }
    }
}

long long calc(long long p) {
    long long ret = 0, dup = n;

    while (dup /= p)
    ret += dup;

    return ret;
}

void factorize(long long num) {
    while (num > 1) {
        long long p = E[num], cnt = 0;

        while (num % p == 0) {
            num /= p;
            cnt++;
        }

        long long req = calc(p);
        res = min(res, req / cnt);
    }
}

int main() {
    sieve();

    cin >> n >> t;
    while (t--) {
        cin >> k;

        res = LLONG_MAX;
        factorize(k);

        cout << res << " ";
    }

    return 0;
}

:::

## Chuyên đề: Tìm kiếm nhị phân

### Đếm số

Trước tiên cần ==sắp xếp== mảng $A$ tăng dần. Sau dó, với mỗi truy vấn `u v`:
- Gọi $x$ là chỉ số ==đầu tiên== sao cho $A_x \ge u$.
- Gọi $y$ là chỉ số ==cuối cùng== sao cho $A_y \le v$.
- Đáp án là: ==$y - x + 1$==

Việc tìm $x$ và $y$ có thể thực hiện bằng tìm kiếm nhị phân.

>[!Tip]
> Sử dụng hàm `lower_bound` và `upper_bound` có sẵn của C++:
> - `x = lower_bound(A+1, A+1+n, u) - A`
> - `y = upper_bound(A+1, A+1+n, v) - A - 1`

:::danger
**Lưu ý:** Đề bài không cho điều kiện $u \le v$, do đó cần cẩn thận tránh việc in ra kết quả là số âm.
:::

:::success
:::spoiler Code

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(VCT) VCT.begin(), VCT.end()
#define pb push_back
using namespace std;

const int N = 1e5;
int n, q, A[N+1];

int32_t main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> A[i];

    sort(A+1, A+1+n);
    while (q--) {
        int l, r;
        cin >> l >> r;

        l = lower_bound(A+1, A+1+n, l) - A;
        r = upper_bound(A+1, A+1+n, r) - A - 1;

        cout << max(0LL, r-l+1) << "\n";
    }
}

:::

### Trò chơi với dãy số

>[!Tip] Nhận xét
>Với mỗi giá trị $A_i$, nhận thấy cần tìm $B_j$ ==gần bằng== $A_i$ nhất để $|A_i + B_j|$ nhỏ nhất. Có thể dễ dàng thực hiện điều này bằng ==tìm kiếm nhị phân==.

Trước tiên cần ==sắp xếp== mảng $B_j$ tăng dần. Sau đó, với mỗi giá trị $A_i$, ta thực hiện:
- Tìm kiếm $B_j$ nhỏ nhất thỏa $B_j \ge A_i$.
- Tìm kiếm $B_j$ lớn nhất thỏa $B_j \le A_i$.
- Cập nhật đáp án với kết quả nhỏ nhất.

:::success
:::spoiler Code

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(VCT) VCT.begin(), VCT.end()
#define pb push_back
using namespace std;

const int N = 1e5;
int n, q, A[N+1], B[N+1], res = 1e18;

int32_t main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> A[i];
    for (int i = 1; i <= n; i++) cin >> B[i];

    sort(B+1, B+1+n);
    for (int i = 1; i <= n; i++) {
        int x = lower_bound(B+1, B+1+n, -A[i]) - B;
        if (x >= 1 && x <= n) res = min(res, abs(A[i] + B[x]));

        x--;
        if (x >= 1 && x <= n) res = min(res, abs(A[i] + B[x]));
    }

    cout << res;
}

:::

### Sushi

>[!Tip] Mô hình hóa bài toán:
> Xét mỗi vị trí $i$, ta sẽ đi tìm độ dài của ==đoạn dài nhất hợp lệ== kết thúc tại $i$.
> - Tìm vị trí $j$ nhỏ nhất thỏa $A_{j+1} = A_{j+2} = \dots = A_i$
> - Tìm vị trí $k$ nhỏ nhất thỏa $A_{k+1} = A_{k+2} = \dots = A_{j}$.
>
> Khi đó, độ dài của đoạn dài nhất kết thúc tại $i$ là:
> $$
> \min \left( i - j, j - k \right) \cdot 2
> $$

Bài toán tổng quát cần giải là tìm vị trí $j$ nhỏ nhất thỏa $A_{j+1} = A_{j+2} = \dots = A_i$. Có thể thực hiện điều trên bằng ==tìm kiếm nhị phân== kết hợp với ==mảng cộng dồn==:

Không mất tính tổng quát, giả sử $A_i = 1$ (vì cách làm tương tự cho $A_i = 2$).
- Gọi $S_i$ là số lượng số $2$ xuất hiện trong mảng $A$ từ $1$ đến $i$. Khi đó, $S$ là một mảng tăng dần, cho phép tìm kiếm nhị phân.
- Vị trí $j$ nhỏ nhất thỏa $S_j = S_i$ cũng chính là $j$ nhỏ nhất để $A_{j+1} = A_{j+2} = \dots = A_i$

Đáp án: Lấy độ dài tối đa ở từng vị trí.

**Độ phức tạp thời gian:** $O \left( n \log n \right)$.

:::success
:::spoiler Code

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

const int N = 1e5;
int n, res, A[N+1], S[2][N+1];

int32_t main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        A[i]--;

        for (int j = 0; j <= 1; j++) S[j][i] = S[j][i-1] + (A[i] == j);
    }

    for (int r = 2; r <= n; r++) {
        int mid = lower_bound(S[!A[r]] , S[!A[r]] + n, S[!A[r]][r]) - S[!A[r]];
        if (!mid) continue;

        int l = lower_bound(S[!A[mid]] , S[!A[mid]] + n, S[!A[mid]][mid]) - S[!A[mid]];
        res = max({res, min((r - mid) * 2, (mid - l) * 2)});

        //cout << r << " " << mid << " " << l << "\n";
    }

    cout << res;

    return 0;
}

:::

## Chuyên đề: Quy hoạch động

### Thuê phòng họp

>[!Tip]
>Trước tiên cần sắp xếp các giờ họp theo một trật tự nhất định (tăng dần theo giờ bắt đầu hoặc tăng dần theo giờ kết thúc). Từ đó, ta mới có thể định nghĩa trạng thái quy hoạch động..

- **Định nghĩa:** ==$dp_i$== là tổng số tiền lớn nhất thu được khi xét $i$ giờ họp đầu tiên, chọn một số giờ họp, bắt buộc phải lấy giờ họp thứ $i$.
- **Khởi gán:** ==$dp_i = C_i$== với $i$ từ $1$ đến $n$ (trường hợp chỉ lấy duy nhất giờ họp thứ $i$).
- **Công thức:** ==$dp_i = \max \left( dp_i, dp_j + C_i \right)$== với $j \lt i$ và $B_j \le A_i$ (tức là thêm cuộc họp thứ $i$ vào chuỗi các cuộc họp tối ưu đã kết thúc bằng cuộc họp thứ $j$).
- **Kết quả:** $\max(dp_i)$ với $i$ từ $1$ đến $n$.

**Độ phức tạp thời gian:** $O \left( n^2 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
const int N = 1e4;
int n;
pair<pii, int> A[N+1];
ll F[N+1], res;

bool cmp(pair<pii, int> a, pair<pii, int> b) {
    return (a.fi.fi < b.fi.fi);
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
        cin >> A[i].fi.fi >> A[i].fi.se >> A[i].se;

    sort(A+1, A+1+n, cmp);
    for (int i = 1; i <= n; i++) {
        F[i] = A[i].se;
        for (int j = 1; j < i; j++)
            if (A[i].fi.fi >= A[j].fi.se)
                F[i] = max(F[i], F[j] + A[i].se);

        res = max(res, F[i]);
    }

    cout << res;

	return 0;
}

:::

### Đoàn kiến

- **Định nghĩa:** ==$dp_i$== là tổng thời gian nhỏ nhất để $i$ con kiến đầu tiên có thể đi qua an toàn.
- **Khởi gán:** ==$dp_0 = 0$==.
- **Công thức:** ==$dp_i = \min \left( dp_i, dp_j + T_{j+1, i} \right)$== với $1 \le i \le n$, $0 \le j \lt i$ và $k_{j+1} + k_{j+2} + \dots + k_i \le m$:
- $T_{j+1, i}$ là thời gian để các con kiến $j+1, j+2, \dots, i$ đi qua an toàn.
- Công thức trên nghĩa là tách các con kiến $j+1, j+2, \dots, i$ thành một nhóm, và ghép với cách tối ưu để những con kiến trước đó (từ $1$ đến $j$) đã đi qua.
- **Kết quả:** ==$dp_n$==.

**Độ phức tạp thời gian:** $O \left( n^2 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1000;
ll n, m, l, K[N+1], V[N+1];
double F[N+1];

int main() {
    cin >> n >> m >> l;
    for (int i = 1; i <= n; i++)
        cin >> K[i] >> V[i];

    for (int i = 1; i <= n; i++) {
        ll sum = K[i], velo = V[i];
        F[i] = F[i-1] + double(l)/velo;

        for (int j = 1; sum + K[i-j] <= m && j < i; j++) {
            sum += K[i-j];
            velo = min(velo, V[i-j]);
            F[i] = min(F[i], F[i-j-1] + double(l)/velo);
        }
    }

    cout << fixed << setprecision(2) << F[n];

	return 0;
}

:::

### Cóc nhảy

- **Định nghĩa:** ==$dp_i$== là chi phí nhỏ nhất để con ếch nhảy đến hòn đá thứ $i$.
- **Khởi gán:** ==$dp_1 = 0$==.
- **Công thức:** ==$dp_i = \min \left( dp_i, dp_j + |H_i - H_j| \right)$== với $2 \le i \le n$ và $i-k \le j \lt i$. Nghĩa là cho ếch nhảy từ $j$ đến $i$, cộng thêm chi phí của bước nhảy này vào chi phí nhỏ nhất để đến $i$.
- **Kết quả:** ==$dp_n$==.

**Độ phức tạp thời gian:** $O \left( n \cdot k \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const long long N = 2e5 + 5;
int dp[N], h[N], n, k;

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

    dp[1] = 0; 

    for (int i = 2; i <= n; i ++){

        int min_of_al_J = 1e18;

        for (int j = 1; j <= k; j ++)
            if (i - j >= 1)
                min_of_al_J = min(min_of_al_J, dp[i - j] + abs(h[i] - h[i - j]));

        dp[i] = min_of_al_J;
    }

    cout << dp[n];

    return 0;
}

:::

### Kỳ nghỉ dưỡng

- **Định nghĩa:**
- ==$dpa_i$== là số điểm hạnh phúc tối đa của Taro sau khi anh ấy bơi vào ngày $i$.
- ==$dpb_i$== là số điểm hạnh phúc tối đa của Taro sau khi anh ấy bắt bọ vào ngày $i$.
- ==$dpc_i$== là số điểm hạnh phúc tối đa của Taro sau khi anh ấy làm bài vào ngày $i$.
- **Khởi gán:** ==$dpa_0 = dpb_0 = dpc_0 = 0$==.
- **Công thức:** *(bám vào yêu cầu của đề là không được làm cùng hoạt động trong hai ngày liên tiếp)*
- ==$dpa_i = \max \left( dpb_{i-1}, dpc_{i-1} \right) + A_i$==
- ==$dpb_i = \max \left( dpa_{i-1}, dpc_{i-1} \right) + B_i$==
- ==$dpc_i = \max \left( dpa_{i-1}, dpb_{i-1} \right) + C_i$==
- **Kết quả:** ==$\max(dpa_n, dpb_n, dpc_n)$==.

**Độ phức tạp thời gian:** $O \left( n \cdot k \right)$.

:::success
:::spoiler Code

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

const int mx = 1e5 + 11;

int dp[mx][3];

main() {
    int N; cin >> N;
    for(int i = 1; i <= N; ++i) {
        int a, b, c; cin >> a >> b >> c;
        dp[i][0] = max(dp[i - 1][1] + a, dp[i - 1][2] + a);
        dp[i][1] = max(dp[i - 1][0] + b, dp[i - 1][2] + b);
        dp[i][2] = max(dp[i - 1][0] + c, dp[i - 1][1] + c);
    }

    cout << max({dp[N][0], dp[N][1], dp[N][2]}) << endl;
    
    return 0;
}

:::