Advertisement
YEZAELP

CUBE-168: c_o_d_e_c_u_b_e - bottom up

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