fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std ;
  4. int n = 0 ;
  5. ll a[405] ;
  6. ll dp[405],vis[405] ;
  7. ll bt(int pos)
  8. {
  9.     if (pos == n)
  10.         return 0 ;
  11.     if (vis[pos] == 1)
  12.         return dp[pos] ;
  13.     ll res = bt(pos+1) + a[pos]+ a[pos+1] ;
  14.     if (pos < n-2 && pos > 0)
  15.         res = min(res,(bt(pos-1) + a[pos]+ a[pos-1])) ;
  16.     vis[pos] = 1 ;
  17.     dp[pos] = res ;
  18.     return res ;
  19. }
  20. int main()
  21. {
  22.     cin >> n ;
  23.     for (int i = 0 ; i < n ; i++)
  24.         cin >> a[i] ;
  25.     ll x = bt(0) ;
  26.     cout << x << "\n" ;
  27.  
  28.  
  29.     return 0 ;
  30. }
  31.  
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/rNLlWS
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!