結果
問題 | No.874 正規表現間距離 |
ユーザー |
![]() |
提出日時 | 2019-08-30 21:43:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 3,886 bytes |
コンパイル時間 | 2,599 ms |
コンパイル使用メモリ | 212,600 KB |
最終ジャッジ日時 | 2025-01-07 15:49:27 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 38 |
ソースコード
#pragma GCC optimize ("Ofast")#include<bits/stdc++.h>using namespace std;inline void rd(char &c){int i;for(;;){i = getchar_unlocked();if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){break;}}c = i;}inline int rd(char c[]){int i, sz=0;for(;;){i = getchar_unlocked();if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){break;}}c[sz++] = i;for(;;){i = getchar_unlocked();if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){break;}c[sz++] = i;}c[sz]='\0';return sz;}inline void wt_L(char a){putchar_unlocked(a);}inline void wt_L(int x){char f[10];int m=0, s=0;if(x<0){m=1;x=-x;}while(x){f[s++]=x%10;x/=10;}if(!s){f[s++]=0;}if(m){putchar_unlocked('-');}while(s--){putchar_unlocked(f[s]+'0');}}template<class S, class T> inline S chmin(S &a, T b){if(a>b){a=b;}return a;}char A[2002];char B[2002];int As;int Bs;int Ar[2002];int Br[2002];int dp[2002][2002];int solve(int x, int y){int k, res=1073709056;if(dp[x][y] >= 0){return dp[x][y];}if(x-1 >= 0 && Ar[x-1]){chmin(res, solve(x-1, y));}if(y-1 >= 0 && Br[y-1]){chmin(res, solve(x, y-1));}if(x-1 >= 0){chmin(res, solve(x-1, y) + 1);}if(y-1 >= 0){chmin(res, solve(x, y-1) + 1);}if(x-1 >= 0 && y-1 >= 0){if(A[x-1] == B[y-1]){k =0;}else{k =1;}chmin(res, solve(x-1, y-1) + k);if(Ar[x-1]==1){chmin(res, solve(x, y-1) + k);}if(Br[y-1]==1){chmin(res, solve(x-1, y) + k);}}return dp[x][y] = res;}int main(){int i, k, res;As = rd(A);Bs = rd(B);k = 0;for(i=0;i<(As);i++){if(i+1 < As && (A[i+1] == '?' || A[i+1] == '*')){A[k++] = A[i];if(A[i+1] == '*'){Ar[k-1] = 1;}if(A[i+1] == '?'){Ar[k-1] = 2;}i++;continue;}A[k++] = A[i];}As = k;k = 0;for(i=0;i<(Bs);i++){if(i+1 < Bs && (B[i+1] == '?' || B[i+1] == '*')){B[k++] = B[i];if(B[i+1] == '*'){Br[k-1] = 1;}if(B[i+1] == '?'){Br[k-1] = 2;}i++;continue;}B[k++] = B[i];}Bs = k;for(i=0;i<(As+1);i++){int j;for(j=0;j<(Bs+1);j++){dp[i][j] = -1;}}dp[0][0] = 0;res = solve(As, Bs);wt_L(res);wt_L('\n');return 0;}// cLay varsion 20190830-1// --- original code ---// char A[2002], B[2002];// int As, Bs, Ar[2002], Br[2002];//// int dp[2002][2002];//// int solve(int x, int y){// int k, res = int_inf;//// if(dp[x][y] >= 0) return dp[x][y];//// if(x-1 >= 0 && Ar[x-1]) res <?= solve(x-1, y);// if(y-1 >= 0 && Br[y-1]) res <?= solve(x, y-1);//// if(x-1 >= 0) res <?= solve(x-1, y) + 1;// if(y-1 >= 0) res <?= solve(x, y-1) + 1;//// if(x-1 >= 0 && y-1 >= 0){// k = if[A[x-1] == B[y-1], 0, 1];// res <?= solve(x-1, y-1) + k;// if(Ar[x-1]==1) res <?= solve(x, y-1) + k;// if(Br[y-1]==1) res <?= solve(x-1, y) + k;// }//// return dp[x][y] = res;// }//// {// int i, k, res;// rd(A@As, B@Bs);//// k = 0;// rep(i,As){// if(i+1 < As && (A[i+1] == '?' || A[i+1] == '*')){// A[k++] = A[i];// if(A[i+1] == '*') Ar[k-1] = 1;// if(A[i+1] == '?') Ar[k-1] = 2;// i++;// continue;// }// A[k++] = A[i];// }// As = k;//// k = 0;// rep(i,Bs){// if(i+1 < Bs && (B[i+1] == '?' || B[i+1] == '*')){// B[k++] = B[i];// if(B[i+1] == '*') Br[k-1] = 1;// if(B[i+1] == '?') Br[k-1] = 2;// i++;// continue;// }// B[k++] = B[i];// }// Bs = k;//// rep(i,As+1) rep(j,Bs+1) dp[i][j] = -1;// dp[0][0] = 0;// res = solve(As, Bs);// wt(res);// }