---
title{[QUY HOẠCH ĐỘNG CƠ BẢN] - Lời giải}
---

[QUY HOẠCH ĐỘNG CƠ BẢN] - Lời giải
===

-----
###### ✍️ Author: 2School Guideline
#### 📋 Content:
[toc]

-----

## Bài 1:
>Một hàng người đang xếp hàng mua vé được đánh số từ $1$ tới $n$ theo thứ tự từ trên xuống. Một người có thể nhờ người phía trên mình mua giúp mình và rời hàng. Cho $t[i]$ là thời gian để người thứ $i$ mua 1 vé, $r[i]$ là thời gian để người thứ $i$ mua giúp người thứ $i+1$. Tìm thời gian ngắn nhất để mỗi người đều có $1$ vé.

### Ý tưởng:
- Gọi $dp[i]$ là thời gian nhanh nhất để mỗi người đều có vé nếu $i$ là người cuối cùng của hàng.
- Nhận xét:
- Nếu người thứ $i$ tự mua vé:
- Lúc này, do thời gian mua vé của người thứ $i$ không phụ thuộc vào người thứ $i-1$ nên ta có công thức:
- $dp[i] = dp[i-1] + t[i]$.
- Nếu người thứ $i$ nhờ mua vé:
- Vì lúc này thời gian mua vé của người thứ $i$ phụ thuộc vào người thứ $i-1$ nhưng phụ thuộc vào người thứ $i-2$ nên ta có công thức:
- $dp[i] = dp[i-2] + r[i-1]$.
- Từ $2$ nhận xét trên, ta có được công thức:
$\begin{cases}
dp[0] = 0 \\
dp[1] = t_1 \\
dp[i] = \min(dp[i-1] + t[i], dp[i-2] + r[i-1]),\ \ \ 2 \leq i \leq n \\
\end{cases}$
- Vậy đáp án của bài toán là $dp[n]$.
### Code mẫu:

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 1;
typedef long long ll;
int n;
ll t[N], r[N], dp[N];

void read() {
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> t[i];
  for (int j = 1; j < n; ++j) cin >> r[j];
}

void solve() {
  // Bài toán cơ sở
  dp[0] = 0, dp[1] = t[1];
  for (int i = 2; i <= n; ++i) {
    // Công thức truy hồi
    dp[i] = min(dp[i - 1] + t[i], dp[i - 2] + r[i - 1]);
  }
  // Kết quả
  cout << dp[n];
}

int main() {
  read();
  solve();
  return 0;
}

- Độ phức tạp: $O(n)$.

## Bài 2:
> Văn bản là một dãy gồm $n$ từ đánh số từ $1$ đến n. Từ thứ $i$ có độ dài là $w[i]$. Phân trang là một cách xếp lần lượt các từ của văn bản vào dãy các dòng, mỗi dòng có độ dài tối đa là $l$. Ta gọi hệ số phạt của mỗi dòng trong cách phân trang là hiệu số $l - s$, trong đó $s$ là tổng độ dài của các từ xếp trên dòng đó. Hệ số phạt của cách phân trang là giá trị lớn nhất trong số các hệ số phạt của các dòng. Tìm cách phân trang với hệ số phạt nhỏ nhất.

### Ý tưởng:
- Gọi $dp[i]$ là hệ số phạt nhỏ nhất sau khi phân trang xong từ thứ $i$.
- Nhận xét, khi xét tới từ thứ $i$:
- Ta cần tìm cách phân trang mới để đảm bảo hệ số phạt nhỏ nhất.
- Duyệt qua các từ thứ $i(1\leq i\leq n)$, những từ có thể được tách ra xếp thành dòng mới với từ thứ i có công thức: $dp[i] = max(dp[i - 1], l - w[i])$.
- Duyệt qua các từ thứ $j$ ($1 \leq j < i)$, gần nhất với $i$. Nếu trên dòng đó, các từ ghép với từ thứ $i$ có độ dài không quá $l$, ta có:
- Gọi $hsp$ là hệ số phạt hiện tại, ta có công thức $hsp = max(dp[j - 1], l - cur)$ với $cur$ là độ dài hiện tại của dòng đang xét.
- Suy ra: $dp[i] = min(dp[i], hsp)$
- Như vậy, đáp án của bài toán là $dp[n]$.
### Code mẫu:

#include <bits/stdc++.h>

using namespace std;
const int N = 6e3 + 1;
int n, w[N], l, dp[N], s[N];

void read() {
  cin >> n >> l;
  for (int i = 1; i <= n; ++i) {
    cin >> w[i];
    s[i] = s[i - 1] + w[i];
  }
}

void solve() {
  for (int i = 1; i <= n; ++i) {
    // Những từ có thể được tách ra xếp thành dòng mới với từ thứ i
    dp[i] = max(dp[i - 1], l - w[i]);
    for (int j = i - 1; j > 0; --j) {
      // Xét độ dài của dòng đã vượt quá l chưa
      int cur = s[i] - s[j - 1];
      if (cur > l) 
        break;
      // Hệ số phạt của cách phân trang mới
      int hsp = max(dp[j - 1], l - cur);
      // So sánh hệ số phạt mới với hệ số phạt cũ cho cách phân trang của từ thứ i
      dp[i] = min(dp[i], hsp);
    }
  }
  cout << dp[n];
}

int main() {
  read();
  solve();
  return 0;
}

- Độ phức tạp: $O(n^2)$.

## Bài 3:
> Cho bảng $a$ kích thước $m$ x $n$, trên đó ghi các số nguyên $a[i][j]$. Một người xuất phát tại ô nào đó của cột $1$, cần sang cột $n$ tại bất kỳ ô nào.
> Cách di chuyển của người đó theo qui tắc: Từ ô $(i, j)$ có thể đi đến ô $(i-1, j+1), (i, j+1)$ và $(i+1, j+1)$. Tìm đường đi có tổng lớn nhất.
### Ý tưởng:
- Gọi $dp[i][j]$ là tổng đường đi lớn nhất để đi tới vị trí $(i, j)$.
- Nhận xét: Theo quy tắc di chuyển, để đi đến ô $(i, j)$ có thể đi từ các ô $(i-1, j-1)$, $(i, j-1)$ và $(i+1, j-1)$.
- Vì để tính trạng thái của cột $j$, ta cần tính hết trạng thái của cột $j-1$. Như vậy, ta cần ưu tiên tính trạng thái của cột trước khi tính trạng thái của hàng.
- Công thức tổng quát:
$\begin{cases}
dp[i][0] = 0\\
dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 1], dp[i + 1][j - 1]) + a[i][j]
\end{cases}$
- Vì một số trường hợp có ô $(i-1,j-1)$ và $(i+1, j-1)$ nằm ngoài bảng nên ta không tính những giá trị đó.
- Đáp án của bài toán sẽ là $max(dp[i][n])\ \forall\ \ 1\leq i\leq m$ .
### Code mẫu:

#include <bits/stdc++.h>

using namespace std;
const int N = 1e3 + 1;
const int minv = -(1e6 + 1);
int m, n, a[N][N], dp[N][N];

void read() {
  cin >> m >> n;
  for (int i = 1; i <= m; ++i)
    for (int j = 1; j <= n; ++j) 
      cin >> a[i][j];
}

void solve() {
  // Gán giá trị nhỏ nhất các phần tử ngoài mảng để đảm bảo không dùng nó để tính cho các giá trị trên đường đi lớn nhất
  for (int j = 1; j <= n; ++j) {
    dp[0][j] = dp[m + 1][j] = minv;
  }
  
  for (int j = 1; j <= n; ++j)
    for (int i = 1; i <= m; ++i)
      // Công thức truy hồi
      dp[i][j] = max(max(dp[i - 1][j - 1], dp[i][j - 1]), dp[i + 1][j - 1]) + a[i][j];
  
  int ans = minv;
  for (int i = 1; i <= m; ++i) 
    ans = max(ans, dp[i][n]);
  cout << ans;
}

int main() {
  read();
  solve();
  return 0;
}

- Độ phức tạp: $O(n \cdot m)$.

## Bài 4:
> Cho một hình chữ nhật kích thước $a \times b$. Mỗi bước, chọn một hình chữ nhật và cắt nó làm $2$ hình chữ nhật khác, sao cho độ dài các cạnh của $2$ hình chữ nhật đó là số nguyên. Tính số bước ít nhất để cắt hình chữ nhật ban đầu thành những hình vuông.

### Ý tưởng:
- Gọi $dp[w][h]$ là số lần cần cắt để cắt hình chữ nhật $w \times h$ thành các hình vuông.
- Xét một hình chữ nhật $w \times h$:
- Nếu $w = h$ thì đây đã là hình vuông $\rightarrow dp[w][h] = 0$.
- Trong trường hợp $w≠h$, ta có hai lựa chọn cắt theo chiều ngang hoặc chiều dọc:
- Cắt hình chữ nhật $w$ x $h$ theo chiều ngang tại vị trí $k$ sẽ tạo thành $2$ hình chữ nhật có kích thước $w \times k$ và $w \times (h-k)$ $\rightarrow dp[w][h] = dp[w][k] + dp[w][h-k] +1$.
- Cắt hình chữ nhật $w$ x $h$ theo chiều dọc tại vị trí $k$ sẽ tạo thành $2$ hình chữ nhật có kích thước $k \times h$ và $(w-k) \times h$ $\rightarrow dp[w][h] = dp[k][h] + dp[w-k][h] +1$.
- Ta xét với từng vị trí $k$ để chọn ra $dp[w][h]$ nhỏ nhất.
- Như vậy, đáp án ta cần tìm là $dp[w][h]$.

### Code mẫu:

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

const int maxN = 505;

int w, h, dp[maxN][maxN];
 
int main() {
  cin >> w >> h;
  for (int i = 0; i <= w; ++i) {
    for (int j = 0; j <= h; ++j) {
      if(i == j){
        dp[i][j] = 0;
      }
      else{
        dp[i][j] = 1e9;
        for (int k = 1; k < i; ++k) {
          dp[i][j] = min(dp[i][j], dp[k][j] + dp[i - k][j] + 1);
        }
        for (int k = 1; k < j; ++k) {
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j - k] + 1);
        }
      }
    }
  }
  cout << dp[w][h];
 
  return 0;
}

- Độ phức tạp: $O(ab \cdot (a+b))$