Một số bài toán Quy hoạch động

Viết bài: Trần Gia Huy

Dưới đây là một số bài toán sử dụng phương pháp Quy hoạch động cơ bản mà mình đã hoặc đã từng làm, sol có thể còn sai sót mong nhận được sự thông cảm từ bạn đọc.

$-arigatou$

$gozaimasu-$

Bài 1: LIS - Dãy con tăng dài nhất (bản dễ).

Link chấm bài: https://oj.vnoi.info/problem/liq

Cho mảng số nguyên

$A$ gồm

$n$ phần tử, hãy tìm dãy con (có thể không liên tiếp) tăng dài nhất của mảng

$A$.
Ví dụ:

$A=4,3,6,7$ thì ta có độ dài dãy con tăng dài nhất là

$3$.

Nhận xét:

• Gọi
  $dp[i]$ là độ dài dãy con tăng dài nhất kết thúc ở
  $a_i$. Ta dễ dàng nhận ra độ dài của dãy con dài nhất ta có ở trường hợp cơ sở là
  $1$.
• Với
  $i<j$ mà
  $a_j>a_i$ thì ta có thể thêm
  $a_i$ vào dãy con tăng kết thúc ở
  $a_j$ .
• Khi đó ta chỉ cần so sánh
  $dp[i]$ của hiện tại với
  $dp[j]+1$ nghĩa là độ dài dãy con hiện tại đã tính được và độ dài dãy con vừa được tính xem cái nào lớn hơn thì ta sẽ cập nhật kết quả.
• Công thức quy hoạch động:
  $dp[i]=max(dp[i],dp[j]+1)$.
• Độ phức tạp thời gian:
  $O(n^2)$.

Code:

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

int main() {
    int n, ans = 1; cin >> n;
    int a[n];
    vector<int> dp(n, 1);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
                ans = max(ans, dp[i]);
            }
        }
    }
    cout << ans;
    return 0;
}

Bài 2: LIS - Dãy con tăng dài nhất (bản khó).

Tuy ý tưởng này không phải DP nhưng thôi cứ note đây :v

Link chấm bài: https://oj.vnoi.info/problem/lis

Đề tương tự như trên nhưng ta sẽ có nhiều phương pháp để tối ưu thời gian chạy thuật toán như Chặt nhị phân, Fenwick tree,…

Ta khởi tạo mảng

$dp$ để lưu dãy con tăng dài nhất, từ đó ta rút ra được nhận xét như sau:

Ban đầu

$dp[1]=a[1]$ vì dãy con tăng dài nhất đầu tiên chỉ chứa một phần tử.

Tiến hành duyệt từ

$a[2]$ trở đi, khi đó xảy ra 3 trường hợp:

Trường hợp 1:

Nếu

$a[i]<dp[1]$ thì ta cập nhật

$dp[1]=a[i]$ để đảm bảo rằng dãy con tăng dài nhất bắt đầu từ

$a[i]$ và chỉ chứa một phần tử.

Trường hợp 2:

Nếu

$a[i]$ lớn hơn phần tử cuối cùng đang xét ở mảng

$dp$ thì ta sẽ tăng biến

$ans$ lên

$1$ đơn vị và gán

$dp[ans]=a[i]$. Khi đó,

$dp[ans]$ chính là phần tử lớn nhất trong dãy con tăng có độ dài

$ans$.

Trường hợp 3:

Nếu

$a[i]$ nằm giữa các phần tử của dãy

$dp$ thì khi đó ta cần tìm vị trí chính xác của nó trong

$dp$ để cập nhật. Rõ ràng nếu

$a[i]$ là phần tử lớn nhất trong dãy

$dp$ thì ta chỉ cần tăng

$ans$ lên

$1$ đơn vị và gán

$dp[ans]=a[i]$ (như trường hợp 2).

Tuy nhiên, nếu

$a[i]$ không phải là phần tử lớn nhất trong

$dp$ thì ta cần tìm vị trí chính xác để chèn vào sao cho dãy

$dp$ vẫn duy trì tính chất tăng dần. Để làm được điều này, ta sử dụng chặt nhị phân kết quả.

Ta tiến hành tìm vị trí

$r$ sao cho

$dp[r]$ là phần tử đầu tiên trong dãy

$dp$ lớn hơn hoặc bằng

$a[i]$, khi tìm được ta gán

$dp[r]=a[i]$.

Code cài đặt bằng Binary Search:

// author : Tran Gia Huy
#include "bits/stdc++.h"
using namespace std;
 
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define maxn 100005

int n, a[maxn], ans = 1;
vector<int> dp(maxn, 0);
void OnePunchAC() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    dp[1] = a[1];
    for (int i = 2; i <= n; i++) {
    	if (a[i] < dp[1]) dp[1] = a[i];
    	else if (a[i] > dp[ans]) dp[++ans] = a[i];
    	else {
            int l = 0, r = ans + 1;
            while (r - l > 1) {
                int m = (l + r) >> 1;
                if (dp[m] >= a[i]) r = m;
                else l = m;
            }
            dp[r] = a[i];
    	}
    }
    cout << ans << '\n';
    //for (int i = 1; i <= n; i++) cout << dp[i] << " "; // Truy vet
}
 
int main() {
    fastIO
    int tt = 1; //cin >> tt;
    while(tt--) OnePunchAC();
    cerr << '\n' << "Times: " << TIME << "s." << '\n';
    return 0;
}

Code cài đặt bằng Fenwick Tree:

/* author : Tran Gia Huy */
#include <bits/stdc++.h>
using namespace std;
 
#define fast_paced ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define builtin_popcount __builtin_popcountll
#define fi first
#define se second
#define p64 pair<long long, long long>
#define p32 pair<int, int>
#define ll long long
#define ull unsigned long long
#define ldb long double
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define maxn 200005

const ldb PI = 3.1415926535897932384626433832795028841971693993751058209749445923, EPS = 1e-6;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e9 + 9;

int n, a[maxn], b[maxn], bit[maxn];
// Might I solve this issue very expeditiously?
void update(int x, int v) {
    for (; x < maxn; x += x & -x) bit[x] = max(bit[x], v);
}
int get(int x) {
    int ans = 0;
    for (; x; x -= x & -x) ans = max(ans, bit[x]);
    return ans;
}
void moon() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int x = get(a[i]) + 1;
        update(a[i], x);
        ans = max(ans, x);
    }
    cout << ans;
}
 
int main() {
    fast_paced
    int tt = 1; //cin >> tt;
    while(tt--) moon();
    cerr << '\n' << "Times: " << TIME << "s." << '\n';
    return 0;
}

/** -------------------- NOTES --------------------

    ----------------------------------------------- **/

Bài 3: Princess.

Link chấm bài:

Ngày xửa ngày xưa có một nàng công chúa dễ thương tên là Farida sống trong lâu đài cùng với cha, mẹ và chú của mình. Trên đường đến lâu đài có nhiều quái vật. Mỗi người trong số họ có một số tiền vàng. Mặc dù chúng là quái vật nhưng chúng sẽ không làm bạn bị thương. Thay vào đó, chúng sẽ đưa cho bạn những đồng tiền vàng, nhưng quái vật thứ

$i$ chỉ đưa vàng cho bạn khi và chỉ khi bạn không lấy bất kì đồng xu nào từ quái vật thứ

$i-1$.

Dữ liệu nhập:

• Dòng đầu tiên chứa số nguyên
  $T$ là số lượng bộ test (
  $1\le T\le 10$).
• Mỗi trường hợp thử nghiệm bắt đầu bằng
  $N$ - số lượng quái vật (
  $0\le N\le {10}^4$).
• Dòng tiếp theo sẽ có
  $N$ số
  $x_1,x_2,...,x_n$ (
  $0\le x_i\le {10}^9$). Với
  $x_i$ là số đồng vàng quái vật thứ
  $i$ có. Quái vật được mô tả theo thứ tự họ gặp trên đường đến lâu đài.

Kết quả:

• In ra
  $T$ dòng, mỗi dòng là một đáp án cho một trường hợp thử nghiệm.

Sample input:

2
5
1 2 3 4 5
1
10

Sample output:

9
10

Nhận xét:

Gọi

$dp[i]$ là số lượng đồng xu nhiều nhất khi lấy đến quái vật thứ

$i$.
Dễ dàng nhận ra trường hợp

$n=0$ nghĩa là không có con quái vật nào hết thì đồng nghĩa với việc số lượng đồng xu nhiều nhất ta có thể đạt được là

$=0$.

$dp[0]=0$

Với

$n>0$ thì ta duyệt từ

$i=2$, khi đó có 2 trường hợp:

Trường hợp 1:

Ta sẽ lấy đồng xu của quái vật thứ

$i-1$, thì ta sẽ không lấy được xu của quái vật thứ

$i$.

Trường hợp 2:

Ta sẽ không lấy xu của quái vật thứ

$i-1$ thì khi đó ta sẽ lấy đồng xu của con quái vật thứ

$i$ đưa cho ta là

$x[i]$.

Công thức quy hoạch động:

$dp[i]=max(dp[i-1],dp[i-2]+x[i])$

Code:

/* author : Tran Gia Huy */
#include <bits/stdc++.h>
using namespace std;
 
#define fast_paced ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define ll long long
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)

const ldb PI = 3.1415926535897932384626433832795028841971693993751058209749445923, EPS = 1e-6;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e9 + 9;

// Might I solve this issue very expeditiously?
void moon() {
    int n; cin >> n;
    ll dp[n + 1], x[n + 1];
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; i++) cin >> x[i];
    dp[0] = 0; // Trường hợp cơ sở
    if (n >= 1) {
        dp[1] = x[1]; 
    }
    for (int i = 2; i <= n; i++) {
        dp[i] = max(dp[i - 1], dp[i - 2] + x[i]);
    }
    cout << dp[n] << '\n';
}
int main() {
    fast_paced
    int tt = 1; cin >> tt;
    while(tt--) moon();
    cerr << '\n' << "Times: " << TIME << "s." << '\n';
    return 0;
}

Bài 4: Chuyển tin (HSG 12 Bến Tre 2021 - 2022).

Link chấm bài :

Cần chuyển hết

$n$ gói tin trên một mạng gồm

$m$ kênh truyền. Biết chi phí chuyển

$i$ gói trên kênh

$j$ là

$C(i,j)$ (

$1\le C(i,j)\le 10000$).

Yêu cầu: cho biết một phương án chuyển gói tin với chi phí thấp nhất.

Dữ liệu:
Dòng đầu tiên gồm hai số

$n$ và

$m$ (

$1<n,m\le 10000$).
Dòng thứ

$i$ trong

$n$ dòng tiếp theo, mỗi dòng gồm dãy

$m$ số nguyên dương

$C_1,C_2,...,C_m$ trong đó

$C_j$ là chi phí chuyển

$i$ gói tin trên kênh

$j$.

Kết quả:
Dòng đầu tiên: tổng chi phí thấp nhất theo phương án tìm được.
Dòng thứ

$j$ trong

$m$ dòng tiếp theo là số lượng gói tin chuyển trên kênh

$j$.

Sample input:

5 4
31 10 1 1
1 31 12 13
4 10 31 1
6 1 20 19
10 5 10 10

Sample output:

2
0
4
1
0

Giải thích: với

$n=5$ gói tin,

$m=4$ kênh và chi phí

$C(i,j)$ cho trước, trong đó

$i$ là chỉ số dòng (số gói tin),

$j$ là chỉ số cột (kênh) thì cách chuyển sau đây cho kết quả chi phí thấp nhất là

$2$.

Kênh	Số gói tin	Chi phí
1	0	0
2	4	1
3	1	1
4	0	0

$31$

$10$

$1$

$1$

$1$

$31$

$12$

$13$

$4$

$10$

$31$

$1$

$6$

$1$

$20$

$19$

$10$

$5$

$10$

$10$

Nhận xét:

Gọi

$dp[i][j]$ là chi phí nhỏ nhất để tạo ra

$i$ gói sử dụng kênh

$j$, nên đáp án là

$dp[n][m]$.

Giả sử tại kênh

$j$ phải sử dụng

$x$ gói thì ta sẽ duyệt for để tính số gói tại kênh

$j$. Vậy thì trạng thái lúc này đang là

$x$ gói tại kênh

$j$ nên ta dễ dàng suy ra được trạng thái trước đó sẽ là

$i-x$ gói tại kênh

$j-1$.

Công thức quy hoạch động:

$dp[i][j]=min(dp[i][j],dp[i-x][j-1]+a[x][j])$.

Ở bài này cần phải truy vết nên ta sẽ khởi tạo một mảng 2 chiều và 1 vector để làm điều đó. Ta khởi tạo biến

$x$ và gán cho nó bằng vết cuối cùng sau khi quy hoạch động, và ta sẽ cập nhật

$res$

$[$kênh thứ

$j$

$]$

$=x$, nghĩa là lưu số gói đã dùng tại kênh

$j$ và cứ như thế ta truy vết tiếp.

Code:

// author : Tran Gia Huy
#include "bits/stdc++.h"
using namespace std;

#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define pf push_front
#define ll long long
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)

int n, m;
int a[101][101], dp[101][101], ans[101][101];  
vector<int> res(101);

void truyvet(int i, int j) {
    if(j == 0) return;
    int x = ans[i][j];
    res[j] = x;
    truyvet(i - x, j - 1);
}      
void solve() {
    memset(dp, 0, sizeof dp); 
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            dp[i][j] = 1e9;
    	}
    }
    for (int i = 1; i <= n; i++) dp[i][1] = a[i][1];
    for (int i = 1; i <= n; i++) {
    	for (int j = 2; j <= m; j++) {
            for (int x = 0; x <= i; x++) { 			
                if (dp[i][j] > dp[i - x][j - 1] + a[x][j]) {
                    dp[i][j] = dp[i - x][j - 1] + a[x][j];
                    ans[i][j] = x;
                }
            }
        }
    }
    cout << dp[n][m] << '\n';
    truyvet(n, m);
    for (int i = 1; i <= m; i++) cout << res[i] << '\n';
}

int main() {
    fastIO
    int t = 1; //cin >> t;
    while(t--) solve();
    cerr << "Times: " << TIME << "s." << endl;
    return 0;
}

Bài 5: