Saleh127

Light OJ 1031/ DP

Nov 11th, 2021 (edited)
583
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-11-20.55.17
  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[205][205];
  13. ll a[205],n;
  14.  
  15. ll solve(ll l,ll r)
  16. {
  17.      if(l>r) return 0;
  18.  
  19.      if(dp[l][r]!=INT_MIN) return dp[l][r];
  20.  
  21.      ll ans=INT_MIN,sum=0;
  22.  
  23.      for(ll i=l;i<=r;i++)
  24.      {
  25.           sum+=a[i];
  26.           ans=max(ans,sum-solve(i+1,r));
  27.      }
  28.      sum=0;
  29.      for(ll i=r;i>=l;i--)
  30.      {
  31.           sum+=a[i];
  32.           ans=max(ans,sum-solve(l,i-1));
  33.      }
  34.  
  35.      dp[l][r]=ans;
  36.  
  37.      return ans;
  38. }
  39.  
  40. int main()
  41. {
  42.    ios_base::sync_with_stdio(0);
  43.    cin.tie(0);cout.tie(0);
  44.  
  45.  
  46.    test
  47.    {
  48.  
  49.         ll i,j,k,l;
  50.  
  51.         cin>>n;
  52.  
  53.         for(i=0;i<n;i++) cin>>a[i];
  54.  
  55.         for(i=0;i<201;i++)
  56.         {
  57.              for(j=0;j<201;j++)
  58.              {
  59.                   dp[i][j]=INT_MIN;
  60.              }
  61.         }
  62.  
  63.         cout<<"Case "<<cs<<": ";
  64.        
  65.         cout<<solve(0,n-1)<<nl;
  66.    }
  67.  
  68.  
  69.    get_lost_idiot;
  70. }
  71.  
RAW Paste Data Copied