Saleh127

Light OJ 1051 / DP - Edit dis

Dec 3rd, 2021
639
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-12-04-09.56.07
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define nl '\n'
  11. string a;
  12. ll dp[55][55][55],n;
  13.  
  14. ll solve(ll in,ll v,ll c)
  15. {
  16.      if(v>=3 || c>=5) return 0;
  17.      if(in==n) return 1;
  18.  
  19.      if(dp[in][v][c]!=-1) return dp[in][v][c];
  20.  
  21.      ll ans;
  22.  
  23.      if(a[in]=='A' || a[in]=='E' || a[in]=='I' || a[in]=='O' || a[in]=='U')
  24.      {
  25.           ans=solve(in+1,v+1,0);
  26.      }
  27.      else if(a[in]=='?')
  28.      {
  29.           ll xx=solve(in+1,v+1,0);
  30.           ll yy=solve(in+1,0,c+1);
  31.  
  32.           if(xx==yy) ans=xx;
  33.           else ans=2;
  34.      }
  35.      else ans=solve(in+1,0,c+1);
  36.  
  37.      return dp[in][v][c]=ans;
  38. }
  39.  
  40.  
  41. int main()
  42. {
  43.    ios_base::sync_with_stdio(0);
  44.    cin.tie(0);cout.tie(0);
  45.  
  46.    test
  47.    {
  48.         cin>>a;
  49.  
  50.         n=a.size();
  51.  
  52.         memset(dp,-1,sizeof dp);
  53.  
  54.         ll x=solve(0,0,0);
  55.  
  56.         cout<<"Case "<<cs<<": ";
  57.  
  58.         if(x==0) cout<<"BAD"<<nl;
  59.         else if(x==1) cout<<"GOOD"<<nl;
  60.         else cout<<"MIXED"<<nl;
  61.  
  62.    }
  63.  
  64.  
  65.  
  66.    get_lost_idiot;
  67. }
  68.  
RAW Paste Data