結果

問題 No.225 文字列変更(medium)
ユーザー BantakoBantako
提出日時 2018-12-31 00:50:52
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,218 bytes
コンパイル時間 1,814 ms
コンパイル使用メモリ 170,228 KB
実行使用メモリ 10,976 KB
最終ジャッジ日時 2024-10-09 13:47:18
合計ジャッジ時間 2,742 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 WA -
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:7:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    7 | main(){
      | ^~~~

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int N,M;
    cin >> N >> M;
    string S,T,R;
    cin >> S >> T;
    int dp[N+1][M+1] = {}, table[N+1][M+1] = {};//↖↑←123
    rep(i,1,N+1)rep(j,1,M+1){
        if(i == 0 || j == 0)dp[i][j] = 0;
        else if(S[i-1] == T[j-1]){
            dp[i][j] = dp[i-1][j-1] + 1;
            table[i][j] = 1;
        }else{
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if(dp[i-1][j] > dp[i][j-1])table[i][j] = 2;
            else    table[i][j] = 3;
        } 
    }
    //cout << dp[N][M] << endl;
    for(int i = N,j = M;table[i][j] != 0;){
        if(table[i][j] == 1){
            R = S[i-1] + R;
            i--,j--;
        }else if(table[i][j] == 2)i--;
        else j--;
    }
    //cout << R << endl;
    int cnt = 0;
    S += "0",T += "0",R += "0";
    for(int i = 0,j = 0,k = 0;i < R.size();i++,j++,k++){
        int d1 = 0, d2 = 0;
        while(R[i] != S[j]){j++;d1++;}
        while(R[i] != T[k]){k++;d2++;}
        cnt += max(d1, d2);

    }
    //cout << cnt << endl;
    cout << max(N,M) - R.size() + 1 << endl;
}
0