fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MAX = 101;
  4.  
  5. //here 60 denotes there is nothing before it
  6. int n;
  7. string s;
  8. vector<vector<int> > dp(MAX,vector<int>(100,-1));
  9.  
  10. int solve(int pos,int last){
  11.  
  12. 	if(dp[pos][last]!=-1) return dp[pos][last];
  13.  
  14. 	if(pos == n) return 0;	
  15. 	int mn = 0,p1 = 0,p2 = 0;
  16. 	p1 = solve(pos+1,s[pos] - 'a');
  17.  
  18. 	if((pos == 0 || last == 60) && s[pos]!='a'){
  19. 		if(pos+1<n && ((s[pos]-'a')-1) == (s[pos+1]- 'a')) p2 = 1+solve(pos+1,last);
  20. 	}
  21. 	else if(s[pos] != 'a' && pos!=0){
  22. 		if((s[pos]-'a')-1 == last) p2 = 1+solve(pos+1,last);
  23. 		else if(pos+1 <n && (s[pos]-'a')-1 == (s[pos+1] - 'a')) p2 = 1+solve(pos+1,last);
  24. 	}
  25.  
  26. 	mn = max(p1,p2);
  27. 	dp[pos][last] = mn;
  28. 	return mn;
  29. }
  30.  
  31.  
  32. int main(){
  33.  
  34. 	ios_base::sync_with_stdio(false);
  35. 	cin.tie(0); cout.tie(0);
  36.  
  37. 	cin>>n>>s;
  38.  
  39. 	if(n==1) return cout<<0<<'\n',0;
  40.  
  41. 	cout<<solve(0,60)<<'\n';
  42. 	return 0;
  43. }
Success #stdin #stdout 0s 4480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/JGqJIU
language:
C++14 (gcc 8.3)
created:
3 years 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!