Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<fstream>
- #include <math.h>
- #include <string>
- using namespace std;
- ifstream cin("strings.in");
- ofstream cout("strings.out");
- long long dp[1000005];
- string s;
- long long inf[30][30];
- long long infi[30][30];
- int main()
- {
- long long a, b, c, i, j, k, l;
- long long mini, maxi;
- cin>>a;
- cin>>s;
- for(i = 0; i<26;i++)
- {
- for(j = 0; j<26; j++)
- {
- infi[i][j] = -1;
- }
- }
- for(i = 0; i<26;i++)
- {
- infi[i][s[0] - 'a'] = 0;
- }
- if(1)
- {
- for(i = 1; i<a;i++)
- {
- long long best = 0;
- while(infi[best][best]==-1){best++;}
- for(j = best + 1; j<26;j++)
- {
- if(infi[s[i]-'a'][j]!=-1)
- {
- 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)))
- {
- best = j;
- }
- }
- }
- dp[i] = inf[s[i]-'a'][best]+(i - infi[s[i] - 'a'][best])*abs((int)(s[i]-'a' - best));
- for(j = 0; j<26;j++)
- {
- if(infi[j][s[i] - 'a']==-1)
- {
- inf[j][s[i] - 'a']= dp[i];
- infi[j][s[i] - 'a']= i;
- }else
- {
- if(dp[i]>inf[j][s[i] - 'a'] + (i - infi[j][s[i] - 'a'])*abs((int)(s[i] - 'a' - j)) )
- {
- infi[j][s[i] - 'a']= i;
- inf[j][s[i] - 'a'] = dp[i];
- }
- }
- }
- }
- /*for(i = 0; i<a;i++)
- {
- cout<<dp[i]<<" ";
- }*/
- cout<<dp[a-1];
- }else
- {
- for(i = 1; i<a;i++)
- {
- for(j = 0; j<i; j++)
- {
- dp[i] = max(dp[i], dp[j] + (i-j)*abs(s[i] - s[j]));
- }
- }
- for(i = 0; i<a;i++)
- {
- cout<<dp[i]<<" ";
- }
- //cout<<dp[i-1];
- }
- }
- /*
- 16
- abccbaeedbaddbad
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement