Saleh127

Light OJ 1217 / DP

Oct 19th, 2021
871
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-10-20-00.44.16
  3. ***/
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define ll long long
  7. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  8. #define get_lost_idiot return 0
  9.  
  10. int main()
  11. {
  12.    ios_base::sync_with_stdio(0);
  13.    cin.tie(0);cout.tie(0);
  14.  
  15.  
  16.    test
  17.    {
  18.         ll n,m,i,j,k,l;
  19.  
  20.         cin>>n;
  21.  
  22.         ll a[n+4];
  23.  
  24.         ll dp[n+4]={0};
  25.  
  26.         for(i=1;i<=n;i++)
  27.         {
  28.              cin>>a[i];
  29.              dp[i]=a[i];
  30.         }
  31.  
  32.         l=0ll;
  33.  
  34.         for(i=2;i<n;i++)
  35.         {
  36.              dp[i]=max(dp[i-2]+a[i],dp[i-1]);
  37.              l=max(l,dp[i]);
  38.         }
  39.  
  40.         dp[1]=0;
  41.  
  42.         for(i=2;i<=n;i++)
  43.         {
  44.              dp[i]=max(dp[i-2]+a[i],dp[i-1]);
  45.              l=max(l,dp[i]);
  46.         }
  47.  
  48.         cout<<"Case "<<cs<<": "<<l<<endl;
  49.    }
  50.  
  51.  
  52.    get_lost_idiot;
  53. }
  54.  
RAW Paste Data