Advertisement
YEZAELP

CUBE-168: c_o_d_e_c_u_b_e - top down

Aug 19th, 2020
100
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.79 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 1e9;
  5. char ar[100010], cmp[] = "codecube";
  6. int l_ar, l_cmp;
  7. vector <vector<int>> dp(100010, vector<int>(10,0));
  8.  
  9. int f(int i, int j){
  10.  
  11.     if(j == l_cmp) return 0;
  12.     if(i == l_ar) return INF;
  13.  
  14.     if(dp[i][j]) return dp[i][j];
  15.  
  16.     if(ar[i] == cmp[j])
  17.         return dp[i][j] = min( f(i+1,j+1), f(i+1,j)+1);
  18.     return dp[i][j] = f(i+1,j)+1;
  19. }
  20.  
  21. int main(){
  22.  
  23.     scanf("%s",ar);
  24.     l_ar = strlen(ar);
  25.     l_cmp = strlen(cmp);
  26.  
  27.     f(0,0);
  28.  
  29.     int mn = INF, idx = -1;
  30.     for(int i=0;i<l_ar;i++){
  31.         if(dp[i][0] < mn){
  32.             mn = dp[i][0];
  33.             idx = i;
  34.         }
  35.     }
  36.  
  37.     if(idx == -1) printf("-1");
  38.     else printf("%d %d",idx+1,idx+8+mn);
  39.  
  40.     return 0;
  41. }
  42. /*
  43. 7 + dp[i][j]
  44. */
  45.  
Advertisement
RAW Paste Data Copied
Advertisement