Advertisement
Saleh127

SPOJ FARIDA / DP

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