YEZAELP

SMMR-119: Message

Jul 1st, 2020 (edited)
100
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. char ar[2010], str[2010];
  5. bool dp[2010][2010];
  6.  
  7. bool DP(int l1,int l2){
  8.     for(int i=l1; i>=0; i--){
  9.         for(int j=l2; j>=0; j--){
  10.             if(i == l1 and j == l2) dp[i][j] = true;
  11.             else if(j == l2) dp[i][j] = false;
  12.             else if(str[j] == '-') dp[i][j] = dp[i+1][j+1];
  13.             else if(str[j] == '$') dp[i][j] = dp[i+1][j+1] or dp[i+1][j] or dp[i][j+1];
  14.             else if(str[j] == ar[i]) dp[i][j] = dp[i+1][j+1];
  15.             else dp[i][j] = false;
  16.         }
  17.     }
  18.     return dp[0][0];
  19. }
  20.  
  21. int main(){
  22.  
  23.     scanf("%s",ar);
  24.     int n;
  25.     scanf("%d",&n);
  26.     for(int i=0;i<n;i++){
  27.         scanf("%s",str);
  28.         if(DP(strlen(ar),strlen(str))) printf("success\n");
  29.         else printf("fail\n");
  30.     }
  31.  
  32.     return 0;
  33. }
  34.  
  35. /**
  36. แบบนี้ก็ได้
  37. bool DP(int n, int m){
  38.  
  39.     for(int i=0;i<=n;i++){
  40.         for(int j=0;j<=m;j++){
  41.             if(i == 0 and j == 0) dp[i][j] = true;
  42.             else if(j == 0) dp[i][j] = false;
  43.             else if(i == 0){
  44.                 // ระวัง! ในกรณีที่ i = 0, j > 0
  45.                 // เช่น str[j] = 'l' -> dp[i][j] = false
  46.                 //     str[j] = '$' -> dp[i][j] = dp[i][j-1] เพราะว่าสามารถข้ามได้ เช่น str = "$$$" สามารถข้ามได้หมดทุกตัว
  47.                 if(str[j-1] == '$') dp[i][j] = dp[i][j-1];
  48.                 else dp[i][j] = false;
  49.             }
  50.             else if(str[j-1] == '$') dp[i][j] = dp[i-1][j] or dp[i][j-1] or dp[i-1][j-1];
  51.             else if(str[j-1] == '-') dp[i][j] = dp[i-1][j-1];
  52.             else if(ar[i-1] == str[j-1]) dp[i][j] = dp[i-1][j-1];
  53.             else dp[i][j] = false;
  54.         }
  55.     }
  56.  
  57.     return dp[n][m];
  58. }
  59.  
  60. **/
RAW Paste Data Copied