fork download
copy 
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4. int main() {
  5.  
  6. 	//Fast I/O
  7. 	ios_base::sync_with_stdio(0);
  8. 	cin.tie(0); cout.tie(0);
  9.  
  10. 	ll n, i;
  11. 	cin >> n;
  12. 	ll a[n], dp1[n], dp21[n], dp22[n], _dp1[n], _dp21[n], _dp22[n], minn1=1000000000, minn2=1000000000;
  13. 	for(i=0; i<n; i++)
  14. 		cin >> a[i];
  15. 	if(n == 1)
  16. 		cout << a[0];
  17. 	else {
  18.  
  19. 		//For case when a[0] is definetely included
  20.  
  21. 		dp1[0] = dp21[0] = dp22[0] = a[0];
  22.  
  23. 		for(i=1; i<n; i++) {
  24. 			dp1[i] = min(dp21[i-1], dp22[i-1]);
  25. 			dp21[i] = dp1[i-1] + a[i];
  26. 			dp22[i] = min(dp21[i-1], dp22[i-1]) + a[i];
  27. 		}
  28.  
  29. 		minn1 = min(dp1[n-1], dp21[n-1]);
  30.  
  31. 		//For case when a[0] is definetely not included
  32.  
  33.  
  34. 		_dp1[0] = _dp21[0] = _dp22[0] = 0;
  35. 		_dp1[1] = a[1];
  36. 		for(i=1; i<n; i++) {
  37. 			if(i > 1)
  38. 				_dp1[i] = min(_dp21[i-1], _dp22[i-1]);
  39. 			_dp21[i] = _dp1[i-1] + a[i];
  40. 			_dp22[i] = min(_dp21[i-1], _dp22[i-1]) + a[i];
  41. 		}
  42.  
  43. 		minn2 = dp21[n-1];
  44.  
  45. 		cout << min(minn1, minn2);
  46. 	}
  47. 	return 0;
  48. }
  49.  
Success #stdin #stdout 0s 4852KB
comments (?)
stdin
copy 
5
1 2 1 2 2
stdout
copy 
4
https://ideone.com/VowhwU
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

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!