fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     string s;
  8.     cin >> s;
  9.  
  10.     int n = s.length();
  11.     int dp[n][3];
  12. 	memset(dp, 0, sizeof(dp));
  13.  
  14.     if (s[0] == 'b')
  15.         dp[0][0] = 1;
  16.     for (int i = 1; i < n; i++) {
  17.  
  18.         if (s[i] == 'b')
  19.             dp[i][0] = dp[i - 1][0] + 1;
  20.         else
  21.             dp[i][0] = dp[i - 1][0];
  22.  
  23.         if (s[i] == 'a')
  24.             dp[i][1] = min(dp[i - 1][0], dp[i - 1][1] + 1);
  25.         else
  26.             dp[i][1] = dp[i - 1][1];
  27.  
  28.         if (s[i] == 'd')
  29.             dp[i][2] = min(dp[i - 1][1], dp[i - 1][2] + 1);
  30.         else
  31.             dp[i][2] = dp[i - 1][2];
  32.     }
  33.  
  34.     cout << "Cost: " << dp[n - 1][2];
  35.     return 0;
  36. }
Success #stdin #stdout 0s 4880KB
comments (?)
stdin
copy 
bbaaddd
stdout
copy 
Cost: 2
https://ideone.com/axXKRI
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!