Advertisement
Guest User

Untitled

a guest
Dec 5th, 2014
440
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.57 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int cost[1000006];
  6. int n;
  7. int ans[1000006];
  8.  
  9. int main()
  10. {
  11.     cin >> n;
  12.     for(int i = 1; i <= n; i++)
  13.     {
  14.         cin >> cost[i];
  15.     }
  16.  
  17.     ans[n - 1] = cost[n - 1];
  18.     ans[n - 2] = cost[n - 2];
  19.     for(int i = n - 3; i > 0; i--)
  20.     {
  21.         ans[i] = cost[i] + min(ans[i + 1], ans[i + 2]);
  22.     }
  23.  
  24.     int curBest = cost[n] + min(ans[1], ans[2]);
  25.  
  26.     ans[n] = cost[n];
  27.     ans[n - 1] = cost[n - 1];
  28.     for(int i = n - 2; i > 0; i--)
  29.     {
  30.         ans[i] = cost[i] + min(ans[i + 1], ans[i + 2]);
  31.     }
  32.  
  33.     curBest = min(curBest, ans[1]);
  34.  
  35.     cout << curBest;
  36. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement