fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define ui unsigned int
  6. #define ul unsigned long long
  7. #define ll long long
  8. #define endl '\n'
  9. #define f first
  10. #define s second
  11. #define int long long
  12.  
  13. int solvi(vector<int>& a, int n){
  14.     vector<int> dp(n+1, 1e18);
  15.     dp[0]=0;
  16.  
  17.     // cout<<v2.size()<<endl;
  18.     // for(auto x:v2) cout<<x<<' ';
  19.     // cout<<endl;
  20.  
  21.     // this is 100 correct for cases where ind!=-1
  22.     for(int i=1; i<=n; i++){
  23.         // if(good2[i]) dp[i]=dp[i-1];
  24.  
  25.         if(i>=2){ // pair us up
  26.             dp[i]=min(dp[i], dp[i-2]+abs(a[i]-a[i-1]));
  27.         }
  28.         if(i>=3){ // can take 3
  29.             vector<int> v1={a[i], a[i-1], a[i-2]}; sort(v1.begin(), v1.end());
  30.             int med=v1[1];
  31.             dp[i]=min(dp[i], dp[i-3]+abs(a[i-2]-med)+abs(a[i-1]-med)+abs(a[i]-med));
  32.         }
  33.         // if(i>=4&&!good2[i]&&!good2[i-1]&&!good2[i-2]&&!good2[i-3]){
  34.         //     vector<int> v1={a[i], a[i-1], a[i-2], a[i-3]}; sort(v1.begin(), v1.end());
  35.         //     int med=v1[1];
  36.         //     dp[i]=min(dp[i], dp[i-4]+abs(a[i-3]-med)+abs(a[i-2]-med)+abs(a[i-1]-med)+abs(a[i]-med));
  37.         // }
  38.     }
  39.     return dp[n];
  40. }
  41.  
  42. void solve(){
  43.     int n; cin>>n;
  44.     int a[2*n]; for(int i=0; i<n; i++) cin>>a[i];
  45.     for(int i=n; i<2*n; i++) a[i]=a[i-n];
  46.  
  47.     // int good[n]{};
  48.     // int ind=-1;
  49.     // for(int i=0; i<n; i++){
  50.     //     good[i]=(a[i]==a[(i-1+n)%n]||a[i]==a[(i+1)%n]);
  51.     //     if(good[i]) ind=i;
  52.     // }
  53.  
  54.     // vector<int> v2; v2.pb(0);
  55.     // vector<int> good2(n+1, 0);
  56.     // if(ind!=-1){
  57.     //     v2.pb(a[ind]);
  58.     //     good2[1]=true;
  59.     //     for(int i=(ind+1)%n; i!=ind; i=(i+1)%n){
  60.     //         good2[v2.size()]=good[i];
  61.     //         v2.pb(a[i]);
  62.     //     }
  63.     // }
  64.     // else{
  65.     //     for(int i=0; i<n; i++){
  66.     //         v2.pb(a[i]);
  67.     //     }
  68.     // }
  69.     // int dp[n+1]{};
  70.  
  71.     int ans=1e18;
  72.     // if(ind!=-1){
  73.     //     ans=solvi(v2, good2, n);
  74.     // }
  75.     // else{
  76.  
  77.     // }
  78.     vector<int> v1; v1.pb(0);
  79.     for(int i=0; i<n; i++) v1.pb(a[i]);
  80.     ans=solvi(v1, n);
  81.  
  82.     v1.clear();
  83.     v1.pb(0); v1.pb(a[n-1]);
  84.     for(int i=0; i<n-1; i++) v1.pb(a[i]);
  85.     ans=min(ans, solvi(v1, n));
  86.  
  87.     v1.clear();
  88.     v1.pb(0); v1.pb(a[n-1]); v1.pb(a[n-2]);
  89.     for(int i=0; i<n-2; i++) v1.pb(a[i]);
  90.  
  91.     ans=min(ans, solvi(v1, n));
  92.  
  93.     v1.clear();
  94.     v1.pb(0); v1.pb(a[n-1]); v1.pb(a[n-2]); v1.pb(a[n-3]);
  95.     for(int i=0; i<n-3; i++) v1.pb(a[i]);
  96.     ans=min(ans, solvi(v1, n));
  97.     cout<<ans<<endl;
  98.  
  99. }
  100.  
  101. int32_t main(){
  102.     ios_base::sync_with_stdio(0);
  103.     cin.tie(0);
  104.  
  105.  
  106.     int t=1;
  107.     cin>>t;
  108.  
  109.     while(t--)
  110.         solve();
  111.  
  112.     return 0;
  113. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/9OOMHB
language:
C++14 (gcc 8.3)
created:
2 days 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!