fork(42) download 
  1. #include<bits//stdc++.h>
  2. using namespace std;
  3. #define INF 1e8
  4. bool check(char a, char b)
  5. {
  6.     if(a==b)
  7.         return 1;
  8.     if(a=='a'&&b=='o')
  9.         return 1;
  10.     if(a=='o'&&b=='a')
  11.         return 1;
  12.     if(a=='t'&&b=='l')
  13.         return 1;
  14.     if(a=='l'&&b=='t')
  15.         return 1;
  16.    return 0;
  17. }
  18.  
  19. int main()
  20. {    
  21.    int n;
  22.    cin>>n;
  23.    string draw_string;
  24.    cin>>draw_string;
  25.    string ticket[n];
  26.    for(int i=0;i<n;i++)
  27.    {
  28.       cin>>ticket[i];
  29.    }
  30.    int k;
  31.    cin>>k;
  32.    int ans=0;
  33.    for(int i=0;i<n;i++)
  34.    {  
  35.       int dp[201][201][2][2];
  36.       int sz2=draw_string.size(),sz1=ticket[i].size();
  37.       for(int j=0;j<sz1;j++)
  38.       {
  39.         dp[j][sz2][0][0]=INF;
  40.         dp[j][sz2][1][0]=INF;
  41.         dp[j][sz2][0][1]=INF;
  42.         dp[j][sz2][1][1]=INF;
  43.       }
  44.       dp[sz1-1][sz2][0][1]=0;
  45.       dp[sz1-1][sz2][1][1]=0;
  46.       for(int j=0;j<=sz2;j++)
  47.       {
  48.         dp[sz1][j][0][0]=0;
  49.         dp[sz1][j][1][0]=0;
  50.         dp[sz1][j][0][1]=0;
  51.         dp[sz1][j][1][1]=0;
  52.       }
  53.       for(int j=sz1-1;j>=0;j--)
  54.       {
  55.         for(int k=sz2-1;k>=0;k--)
  56.         {  
  57.            if(check(ticket[i][j],draw_string[k]))
  58.            {
  59.              dp[j][k][0][0]=min(dp[j+1][k+1][1][0],dp[j][k+1][0][0]);
  60.              dp[j][k][1][0]=dp[j+1][k+1][1][0];
  61.            }
  62.            else
  63.            {
  64.               dp[j][k][0][0]=dp[j][k+1][0][0];
  65.               dp[j][k][1][0]=1+dp[j][k+1][1][0];
  66.            }
  67.            if(check(ticket[i][j],draw_string[k]))
  68.            {
  69.              dp[j][k][0][1]=min(dp[j+1][k+1][1][1],dp[j][k+1][0][1]);
  70.              dp[j][k][1][1]=dp[j+1][k+1][1][1];
  71.            }
  72.            else
  73.            {
  74.               dp[j][k][0][1]=min(dp[j][k+1][0][1],dp[j+1][k+1][0][0]);
  75.               dp[j][k][1][1]=min(1+dp[j][k+1][1][1],dp[j+1][k+1][1][0]);
  76.            }
  77.         }
  78.       }
  79.       if(dp[0][0][0][1]<=k)
  80.         ans++;
  81.     }
  82.    cout<<ans<<endl;
  83.     return 0;
  84. }
Success #stdin #stdout 0s 5396KB
comments (?)
stdin 
3 
aabacd 
abcde 
aoc 
actld 
1
stdout 
2
https://ideone.com/vg1lnr
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!