fork download 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. int lcs(string s, string s1){
  8.     int i,j,n,m;
  9.     n=s.length();
  10.     m=s1.length();
  11.     int dp[n+1][m+1];
  12.     memset(dp, 0, sizeof(dp));
  13.     for(i=1;i<=n;i++){
  14.         for(j=1;j<=m;j++){
  15.             if(s[i-1]==s1[j-1]){
  16.                 dp[i][j]=1+dp[i-1][j-1];
  17.             }else{
  18.                 if(s1[j-1]=='*'){
  19.                     if(s[i-1]==s1[j-2]){
  20.                         dp[i][j]=1+dp[i-1][j];
  21.                     }else{
  22.                         dp[i][j]=max(dp[i][j-2], dp[i-1][j]);
  23.                     }
  24.                 }else{
  25.                     dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
  26.                 }
  27.             }
  28.         }
  29.     }
  30.     /*cout<<"Length= "<<n<<endl;
  31.     for(i=0;i<=n;i++){
  32.         for(j=0;j<=m;j++){
  33.             cout<<dp[i][j]<<" ";
  34.         }
  35.         cout<<endl;
  36.         }*/
  37.     return dp[n][m];
  38. }
  39.  
  40. int main(){
  41.     int t;
  42.     cin>>t;
  43.     while(t--){
  44.         string s;
  45.         cin>>s;
  46.         int a=lcs(s, "0*1*0*");
  47.         int b=lcs(s, "1*0*1*");
  48.         //cout<<" a= "<<a<<" b= "<<b <<endl;
  49.         cout<<(s.length()-max(a, b))<<endl;
  50.     }
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0s 4504KB
comments (?)
stdin 
4
010111101
1011100001011101
0110
111111
stdout 
2
3
0
0
https://ideone.com/DKOm1T
Codechef Purifyit.<br>O(n) solution.
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!