Advertisement
Guest User

Untitled

a guest
Feb 13th, 2018
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.60 KB | None | 0 0
  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. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement