fork download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #define INF 200000000
  5. using namespace std;
  6. typedef long long ll;
  7. int n;
  8. ll a[100010];
  9. ll dp[100011][3];
  10. int main()
  11. {
  12.     int T;
  13.     scanf("%d",&T);
  14.     while(T--)
  15.     {
  16.         scanf("%d",&n);
  17.         for(int i=0;i<n;i++)
  18.             scanf("%lld",&a[i]);
  19.         dp[0][0]=INF;
  20.         dp[0][1]=0;
  21.         dp[0][2]=INF;
  22.         for(int i=0;i<n;i++)
  23.         {
  24.             dp[i+1][0]=min(min(dp[i][0],dp[i][1]),dp[i][2])+a[i];
  25.             dp[i+1][1]=dp[i][0];
  26.             dp[i+1][2]=min(dp[i][0],dp[i][1]);
  27.         }
  28.         printf("%lld\n",min(dp[n][0],dp[n][1]));
  29.     }
  30. }
  31.  
Success #stdin #stdout 0s 6424KB
comments (?)
stdin
copy 
2
5
10 20 30 40 50
3
1 5 3
stdout
copy 
50
4
https://ideone.com/qRJg4P
http://f...content-available-to-author-only...s.org/thread-556-1-1.html
language:
C++14 (gcc 8.3)
created:
9 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!