Solutions of Buying tickets

Select solution language

phphongyd Created at 28 likes

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