fork download
copy 
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4. #define INF numeric_limits<ll>::max()
  5.  
  6. // ll dp[150][100050];
  7.  
  8. ll go(ll val, ll i, ll s, ll b[], ll n)
  9. {
  10.     // cout<<val<<" "<<i<<endl;
  11.  
  12.     if(i==n)
  13.     {
  14.         return s;
  15.     }
  16.  
  17.     // if(dp[val][s]!=-1)
  18.     // {
  19.     //     return dp[val][s];
  20.     // }
  21.  
  22.     ll x = abs(val - b[i]);
  23.     ll y = abs(val - 1);
  24.     // cout<<val<<" "<<i<<" "<<x<<" "<<y<<endl;
  25.     // ll z = abs(1 - b[i]);
  26.     ll sum=0;
  27.     return sum = sum + max(go(b[i], i+1, s+x, b, n), go(1, i+1, s+y, b, n));
  28.     // return dp[val][s] = sum;
  29. }
  30.  
  31. int main() 
  32. {
  33.     ll t;
  34.     cin>>t;
  35.     while(t--)
  36.     {
  37.         ll n;
  38.         cin>>n;
  39.         ll b[n];
  40.         for(ll x=0; x<n; x++)
  41.         {
  42.             cin>>b[x];
  43.         }
  44.  
  45.         // for(ll x=0; x<n; x++)
  46.         // {
  47.         //     cout<<b[x]<<" ";
  48.         // }
  49.         // cout<<endl;
  50.         // memset(dp, -1, sizeof(dp));
  51.         // ll dp[200][101000][201000];
  52.         if(b[0] == 1)
  53.             cout<<go(b[0], 1, 0, b, n)<<endl;
  54.  
  55.         else
  56.             cout<<max(go(b[0], 1, 0, b, n), go(1, 1, 0, b, n))<<endl;
  57.  
  58.     }
  59. 	return 0;
  60. }
  61.  
Success #stdin #stdout 0s 4360KB
comments (?)
stdin
copy 
3
5
10 1 10 1 10
3
1 2 3
5
100 2 100 2 100
stdout
copy 
36
2
396
https://ideone.com/DU8L0B
sherlock and cost recursive solution
language:
C++14 (gcc 8.3)
created:
4 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!