fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7.  
  8. const int INF = 1e9;
  9. const ll LINF = 1e18;
  10.  
  11. const int N = 6e4 + 5;
  12.  
  13. int n;
  14. int t[N];
  15. int r[N];
  16. ll dp[N]; // dp[i] = Tổng thời gian phục vụ bán vé nhỏ nhất khi xét đến người thứ i
  17.  
  18. int main() {
  19. ios::sync_with_stdio(0); cin.tie(0);
  20. cin >> n;
  21. for (int i = 1; i <= n; i++) cin >> t[i];
  22. for (int i = 1; i <= n - 1; i++) cin >> r[i];
  23.  
  24. dp[0] = 0;
  25. dp[1] = t[1];
  26. for (int i = 2; i <= n; i++) {
  27. // Để tính dp[i] thì ta xét 2 trường hợp là người thứ i tự mua vé
  28. // hoặc nhờ người thứ i - 1 mua hộ vé cho cả hai
  29. dp[i] = min(dp[i - 1] + t[i], dp[i - 2] + r[i - 1]);
  30. }
  31.  
  32. cout << dp[n] << '\n';
  33. }
Success #stdin #stdout 0.01s 5320KB
stdin
5
2 5 7 8 4
4 9 10 10
stdout
18