Hiểu rõ bài toán và cách tiếp cận
Bài toán con:
dp[i] là thời gian tối thiểu để bán vé cho i người đầu tiên.
Quan hệ truy hồi:
Để tính dp[i], ta có 2 lựa chọn cho người thứ i:
Tự mua: dp[i] = dp[i-1] + t[i]
Nhờ người trước mua: dp[i] = dp[i-2] + r[i] (vì người thứ i-1 đã được mua vé ở bước trước)
Chọn giá trị nhỏ hơn của hai trường hợp trên để gán cho dp[i].
Điều kiện cơ sở:
dp[1] = t[1] (người đầu tiên tự mua)
Code C++:
```
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, t[N], r[N], dp[N];
int main() {
cin >> n;
for (int i=1;i<=n;i++)cin>>t[i];
for (int i=2;i<=n;i++)cin>>r[i];
dp[1]=t[1];
for (int i = 2; i <= n; ++i) {
dp[i]= min(dp[i-1]+t[i],dp[i-2]+r[i]);
}
cout << dp[n] << endl;
return 0;
}
```
---
# 📝 Lời giải cho bài **Mua vé**
> ⚠️ **KHÔNG NÊN XEM SOLUTION TRỪ KHI QUÁ BÍ Ý TƯỞNG**
## 1. Tóm tắt đề bài
* Có **N** người xếp hàng, mỗi người có thể:
1. Mua **1 vé** cho bản thân → mất `t[i]` thời gian
2. Mua **2 vé** (cho bản thân + người ngay trước) → mất `r[i]` thời gian
* Yêu cầu: Tìm **thời gian nhỏ nhất** để tất cả đều có vé.
---
## 2. Phân tích & suy luận
* Đây là **bài toán tối ưu** → có thể dùng **Dynamic Programming**.
* Định nghĩa:
* `dp[i]` = thời gian nhỏ nhất để **i** người đầu tiên đều có vé.
### Công thức truy hồi
* Trường hợp **tự mua**:
$$
dp[i] = dp[i-1] + t[i]
$$
* Trường hợp **mua luôn cho người phía trước**:
$$
dp[i] = dp[i-2] + r[i-1]
$$
> Lưu ý: Dùng `dp[i-2]` vì khi người $i-1$ mua cho 2 người, ta bỏ qua thời gian của $t[i-1]$.
* **Công thức tổng quát**:
$$
dp[i] = \min\big(dp[i-1] + t[i],\ dp[i-2] + r[i-1]\big)
$$
---
## 3. Khởi tạo
* `dp[0] = t[0]` → chỉ có một người, bắt buộc tự mua.
---
## 4. Hướng duyệt DP
* Cần `dp[i-1]` và `dp[i-2]` → duyệt từ **nhỏ → lớn** (từ `0` đến `n`).
---
## 5. Kết quả
* Đáp án cuối cùng là `dp[n]` → thời gian nhỏ nhất để **n** người đều có vé.
---
## 6. Code minh họa
```cpp
void solve()
{
int n;
cin >> n;
vi t(n), r(n - 1), dp(n);
for (int i = 0; i < n; i++) cin >> t[i];
for (int i = 0; i < n - 1; i++) cin >> r[i];
dp[0] = t[0];
if (n > 1) dp[1] = min(dp[0] + t[1], r[0]);
for (int i = 2; i < n; i++) dp[i] = min(dp[i - 1] + t[i], dp[i - 2] + r[i - 1]);
cout << dp[n - 1] << "\n";
}
```
phphongyd
Created at
37 likes
Phatgivp10
Created at
0 likes