fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. string s;
  6. void nhap(){
  7.     cin >> s;
  8.     s = '0' + s;
  9. }
  10.  
  11. int last[30], dp[100005], f[100005][30], prv[100005][30];
  12. void solve(){
  13.     for(int i = 1; i < s.size(); i++){
  14.         for(int j = 1; j <= 26; j++)prv[i][j] = last[j];
  15.         last[s[i] - 'a' + 1] = i;
  16.     }
  17.     for(int i = 1; i < s.size(); i++){
  18.         int num = 0, d = s[i] - 'a';
  19.         int pos = i;
  20.         while(pos && num < d){
  21.             num++;
  22.             pos = prv[pos][d + 1];
  23.         }
  24.         if(num == d && pos){
  25.             dp[i] = d + 1;
  26.             for(int j = 1; j <= d; j++){
  27.                 dp[i] = max(dp[i], f[pos - 1][j] + d + 1);
  28.             }
  29.         }
  30.         for(int j = 1; j <= 26; j++){
  31.             if(i != 0)f[i][j] = f[i-1][j];
  32.         }
  33.         f[i][d + 1] = max(f[i][d + 1], dp[i]);
  34.     }
  35.     int kq = 0;
  36.     for(int c = 1; c <= 26; c++){
  37.         kq = max(kq, f[s.size() - 1][c]);
  38.     }
  39.     cout << kq;
  40. }
  41.  
  42.  
  43. int main()
  44. {
  45.     ios_base::sync_with_stdio(0);
  46.     cin.tie(0); cout.tie(0);
  47.     nhap();
  48.     solve();
  49.     return 0;
  50. }
  51.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7SuWRD
language:
C++14 (gcc 8.3)
created:
10 days 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!