結果

問題 No.874 正規表現間距離
ユーザー LayCurse
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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);
// }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0