Solutions of Buying tickets - MarisaOJ: Marisa Online Judge

Solutions of Buying tickets

Select solution language

Write solution here.


User Avatar phphongyd    Created at    26 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; } ```