fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define NMAX 305
  3. using namespace std;
  4. int n , k;
  5. int cards[NMAX];
  6. long long dp[NMAX][NMAX][NMAX / 2];
  7. long long ans;
  8.  
  9.  
  10. void maximize(long long &before , long long later)
  11. {
  12.         if(before < later)  before = later;
  13. }
  14.  
  15.  
  16. namespace sub1{
  17.  
  18.       int MaxLater[NMAX] , MinLater[NMAX] , two[NMAX];
  19.  
  20.       void codesub1()
  21.       {
  22.         if(k == 1)
  23.         {
  24.               for(int i = 1 ; i <= n ; i++) 
  25.               for(int j = i + 1 ; j <= n ; j++)  maximize(ans , abs(cards[i] - cards[j]) );
  26.         }
  27.  
  28.         if(k == 2)
  29.         {
  30.                  MaxLater[n] = MinLater[n] = cards[n];
  31.  
  32.                  for(int i = n - 1 ; i >= 1 ; i--)
  33.                  {
  34.                          MaxLater[i] = max(MaxLater[i + 1]  , cards[i]);
  35.                          MinLater[i]  = min(MinLater[i + 1] , cards[i]);
  36.                  }
  37.  
  38.                  for(int i = 2 ; i <= n ; i++)  two[i] = abs(cards[i-1] - cards[i]);
  39.  
  40.                  for(int i = 1 ; i <= n ; i++)  for(int j =  i + 1 ; j <= n ; j++)
  41.                  for(int k = j + 1 ; k < n ; k++)
  42.                        {
  43.                            maximize(ans , abs(cards[i] - MaxLater[k + 1]) + abs(cards[j] - cards[k]) );
  44.  
  45.                            maximize(ans , abs(cards[i] - MinLater[k + 1]) + abs(cards[j] - cards[k]) );
  46.                        }
  47.  
  48.                  for(int i = 2 ; i <= n ; i++)  
  49.                  for(int j = i + 2 ; j <= n ; j++)  maximize(ans , two[i] + two[j]);
  50.               }
  51.  
  52.             cout<<ans;
  53.        }
  54. }
  55.  
  56.  
  57.  
  58. namespace sub2{
  59.  
  60.    void backtrack(int LEFT , int RIGHT , int cnt , long long sum)
  61.    {
  62.         if(cnt == k)
  63.         {
  64.                 maximize(ans , sum );
  65.                 return ;
  66.         }
  67.  
  68.         backtrack(LEFT + 1 , RIGHT - 1 , cnt + 1 , sum + abs(cards[LEFT] - cards[RIGHT]));
  69.  
  70.         backtrack(LEFT + 2 , RIGHT , cnt + 1 , sum + abs(cards[LEFT] - cards[LEFT + 1]));
  71.  
  72.         backtrack(LEFT , RIGHT - 2 , cnt + 1 , sum + abs(cards[RIGHT] - cards[RIGHT - 1] ) );
  73.    }
  74.  
  75.   void codesub2()
  76.   {
  77.         backtrack(1 , n , 0 , 0);
  78.  
  79.         cout<<ans;
  80.   }
  81.  
  82. }
  83.  
  84. namespace sub3{
  85.  
  86.           void codesub3()
  87.           {
  88.                  for(int i = 1 ; i  <= n - 1 ; i++)  dp[i][i+1][1] = abs(cards[i] - cards[i+1]);
  89.  
  90.                  for(int cnt = 1 ; cnt <= k ; cnt++)
  91.                  {
  92.                          for(int length = 3 ; length <= n ; length++)
  93.                          {
  94.                                  for(int LEFT = 1 ; LEFT <= n - length + 1 ; LEFT++)
  95.                                  {
  96.             int RIGHT = LEFT + length - 1;
  97.  
  98.      maximize(dp[LEFT][RIGHT][cnt] , dp[LEFT][RIGHT - 1][cnt]);
  99.  
  100.      maximize(dp[LEFT][RIGHT][cnt] , dp[LEFT + 1][RIGHT][cnt]);
  101.  
  102.      maximize(dp[LEFT][RIGHT][cnt] , dp[LEFT][RIGHT - 2][cnt - 1] + abs(cards[RIGHT] - cards[RIGHT - 1]));
  103.  
  104.      maximize(dp[LEFT][RIGHT][cnt] , dp[LEFT + 2][RIGHT][cnt - 1] + abs(cards[LEFT] - cards[LEFT + 1]));
  105.  
  106.      maximize(dp[LEFT][RIGHT][cnt] , dp[LEFT + 1][RIGHT - 1][cnt - 1] + abs(cards[LEFT] - cards[RIGHT]));
  107.                                  }
  108.                          }
  109.                  }
  110.  
  111.                 cout<<dp[1][n][k];
  112.           }
  113.  
  114. }
  115.  
  116. void process()
  117. {
  118.     cin>> n >> k ;
  119.     for(int i = 1 ;  i<= n ; i++)  cin>>cards[i];
  120.  
  121.     if(n <= 300 && k <= 2)
  122.     { 
  123.         sub1::codesub1();
  124.  
  125.         return;
  126.     }
  127.  
  128.     if(n <= 30 && 2 * k == n)
  129.     { 
  130.         sub2::codesub2();
  131.  
  132.         return;
  133.     }
  134.  
  135.     sub3::codesub3();
  136. }
  137. int main()
  138. {
  139.     ios_base::sync_with_stdio(0);
  140.     cin.tie(nullptr);
  141.     cout.tie(nullptr);
  142.     process();
  143.     return 0;
  144. }
  145.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xaG4oA
language:
C++14 (gcc 8.3)
created:
22 days ago
visibility:
secret

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!