fork(1) download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define str string
  4. #define endl "\n"
  5. #define pb push_back
  6. #define db double
  7. #define fi first
  8. #define se second
  9. #define si size()
  10. using namespace std;
  11. const ll MAXN=8e2+7;
  12. const ll INF=1e16+7;
  13. ll t, n, a[MAXN];
  14. ll dp[807][3], vetcan[807][3] , vetcanlr[807][3];
  15. int main()
  16. {
  17.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  18.     cin >> t;
  19.     while(t--)
  20.     {
  21.         cin >> n;
  22.         for(int i=1;i<=n;i++)
  23.         {
  24.             dp[i][0]=dp[i][1]=INF;
  25.             vetcan[i][0]=vetcan[i][1]=-1;
  26.         }
  27.  
  28.         for(int i=1;i<=n;i++)
  29.         {
  30.             cin >> a[i];
  31.         }
  32.         dp[1][0]=a[1];
  33.  
  34.         // 0 L+ 1 R-
  35.         for(int i=2;i<=n;i++)
  36.         {
  37.             if(abs(dp[i][0])>abs(dp[i-1][0]-a[i]))
  38.             {
  39.                 dp[i][0]=dp[i-1][0]-a[i];
  40.                 vetcan[i][0]=0;
  41.                 vetcanlr[i][0]=1;
  42.             }
  43.             if(abs(dp[i][0])>abs(dp[i-1][1]-a[i]))
  44.             {
  45.                 dp[i][0]=dp[i-1][1]-a[i];
  46.                 vetcan[i][0]=1;
  47.                 vetcanlr[i][0]=1;
  48.             }
  49.             if(abs(dp[i][0])>= abs(dp[i-1][0]+a[i]))
  50.             {
  51.                 dp[i][0]=dp[i-1][0]+a[i];
  52.                 vetcan[i][0]=0;
  53.                 vetcanlr[i][0]=0;
  54.             }
  55.             if(abs(dp[i][0])>=abs(dp[i-1][1]+a[i]))
  56.             {
  57.                 dp[i][0]=dp[i-1][1]+a[i];
  58.                 vetcan[i][0]=1;
  59.                 vetcanlr[i][0]=0;
  60.             }
  61.  
  62.  
  63.             if(abs(dp[i][1])>abs(dp[i-1][0]-a[i]))
  64.             {
  65.                 dp[i][1]=dp[i-1][0]-a[i];
  66.                 vetcan[i][1]=0;
  67.                 vetcanlr[i][1]=1;
  68.             }
  69.             if(abs(dp[i][1])>abs(dp[i-1][1]-a[i]))
  70.             {
  71.                 dp[i][1]=dp[i-1][1]-a[i];
  72.                 vetcan[i][1]=1;
  73.                 vetcanlr[i][1]=1;
  74.             }
  75.             if(abs(dp[i][1])>= abs(dp[i-1][0]+a[i]))
  76.             {
  77.                 dp[i][1]=dp[i-1][0]+a[i];
  78.                 vetcan[i][1]=0;
  79.                 vetcanlr[i][1]=0;
  80.             }
  81.             if(abs(dp[i][1])>=abs(dp[i-1][1]+a[i]))
  82.             {
  83.                 dp[i][1]=dp[i-1][1]+a[i];
  84.                 vetcan[i][1]=1;
  85.                 vetcanlr[i][1]=0;
  86.             }
  87.         }
  88.  
  89.         str s="";
  90.         ll mn=dp[n][0];
  91.         ll pos01 = vetcan[n][0];
  92.         ll poslr = vetcanlr[n][0];
  93.         ll l = 0;
  94.         if(mn > dp[n][1])
  95.         {
  96.             pos01 = vetcan[n][1];
  97.             mn=dp[n][1];
  98.             l = 1;
  99.             poslr = vetcanlr[n][1];
  100.         }
  101.         ll pos1n = n - 1;
  102.         if(poslr==1)
  103.         {
  104.             s='R'+s;
  105.         }else
  106.         {
  107.             s='L'+s;
  108.         }
  109.  
  110.         while(pos1n!=1)
  111.         {
  112.             poslr=vetcanlr[pos1n][pos01];
  113.             if(poslr==1)
  114.             {
  115.                 s='R'+s;
  116.             }else
  117.             {
  118.                 s='L'+s;
  119.             }
  120.             pos01 = vetcan[pos1n][pos01];
  121.             pos1n--;
  122.         }
  123.         cout << "L" << s << endl;
  124.     }
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/kKqZ6H
language:
C++14 (gcc 8.3)
created:
3 hours 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!