daily pastebin goal
69%
SHARE
TWEET

Untitled

a guest Feb 13th, 2018 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<fstream>
  2. #include <math.h>
  3. #include <string>
  4. using namespace std;
  5.  
  6. ifstream cin("strings.in");
  7. ofstream cout("strings.out");
  8.  
  9. long long dp[1000005];
  10. string s;
  11. long long inf[30][30];
  12. long long infi[30][30];
  13.  
  14. int main()
  15. {
  16.     long long a, b, c, i, j, k, l;
  17.     long long mini, maxi;
  18.     cin>>a;
  19.     cin>>s;
  20.    
  21.     for(i = 0; i<26;i++)
  22.     {
  23.         for(j = 0; j<26; j++)
  24.         {
  25.             infi[i][j] = -1;
  26.         }
  27.     }
  28.    
  29.     for(i = 0; i<26;i++)
  30.     {
  31.         infi[i][s[0] - 'a'] = 0;
  32.     }
  33.    
  34.     if(1)
  35.     {
  36.         for(i = 1; i<a;i++)
  37.         {
  38.  
  39.             long long best = 0;
  40.             while(infi[best][best]==-1){best++;}
  41.             for(j = best + 1; j<26;j++)
  42.             {
  43.                 if(infi[s[i]-'a'][j]!=-1)
  44.                 {
  45.                     if(inf[s[i]-'a'][best]+(i - infi[s[i] - 'a'][best])*abs((int)(s[i]-'a' - best)) < inf[s[i]-'a'][j]+(i - infi[s[i] - 'a'][j])*abs((int)(s[i]-'a' - j)))
  46.                     {
  47.                         best = j;
  48.                     }
  49.                 }
  50.             }
  51.  
  52.             dp[i] = inf[s[i]-'a'][best]+(i - infi[s[i] - 'a'][best])*abs((int)(s[i]-'a' - best));
  53.  
  54.             for(j = 0; j<26;j++)
  55.             {
  56.                 if(infi[j][s[i] - 'a']==-1)
  57.                 {
  58.                     inf[j][s[i] - 'a']= dp[i];
  59.                     infi[j][s[i] - 'a']= i;
  60.                 }else
  61.                 {
  62.                     if(dp[i]>inf[j][s[i] - 'a'] + (i - infi[j][s[i] - 'a'])*abs((int)(s[i] - 'a' - j)) )
  63.                     {
  64.                         infi[j][s[i] - 'a']= i;
  65.                         inf[j][s[i] - 'a'] = dp[i];
  66.                     }
  67.                 }
  68.             }
  69.            
  70.  
  71.         }
  72.  
  73.         /*for(i = 0; i<a;i++)
  74.         {
  75.             cout<<dp[i]<<" ";
  76.         }*/
  77.  
  78.         cout<<dp[a-1];
  79.     }else
  80.     {
  81.         for(i = 1; i<a;i++)
  82.         {
  83.             for(j = 0; j<i; j++)
  84.             {
  85.                 dp[i] = max(dp[i], dp[j] + (i-j)*abs(s[i] - s[j]));
  86.             }
  87.         }
  88.         for(i = 0; i<a;i++)
  89.         {
  90.             cout<<dp[i]<<" ";
  91.         }
  92.         //cout<<dp[i-1];
  93.     }
  94.  
  95. }
  96. /*
  97. 16
  98. abccbaeedbaddbad
  99. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top