結果

問題 No.225 文字列変更(medium)
コンテスト
ユーザー Bantako
提出日時 2018-12-31 00:50:52
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,218 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,814 ms
コンパイル使用メモリ 170,228 KB
実行使用メモリ 10,976 KB
最終ジャッジ日時 2024-10-09 13:47:18
合計ジャッジ時間 2,742 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:7:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    7 | main(){
      | ^~~~

ソースコード

diff #
raw source code 

#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