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;
}
```