結果

問題 No.422 文字列変更 (Hard)
コンテスト
ユーザー Hachimori
提出日時 2016-09-10 01:49:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,604 bytes
コンパイル時間 752 ms
コンパイル使用メモリ 58,892 KB
実行使用メモリ 45,120 KB
最終ジャッジ日時 2024-11-17 06:48:43
合計ジャッジ時間 57,506 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 TLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<cstring>
using namespace std;
const int INF = 1<<30;
const int BUF = 1205;

class Next {
public:
    int aPos, bPos;
    int aStart, bStart;
    Next(){}
    Next(int aPos, int bPos, int aStart, int bStart):
        aPos(aPos), bPos(bPos), aStart(aStart), bStart(bStart) {}
};


int aLen, bLen;
string a, b;

void read() {
    cin >> aLen >> bLen;
    cin >> a >> b;
}


void rec(int aPos, int bPos, int dp[BUF][BUF], Next next[BUF][BUF]) {
    int &ret = dp[aPos][bPos];
    Next &nex = next[aPos][bPos];
    
    if (ret != -1) return;
    if (aPos == aLen && bPos == bLen) {
        ret = 0;
        return;
    }
    
    ret = INF;

    // match
    if (aPos < aLen && bPos < bLen) {
        rec(aPos + 1, bPos + 1, dp, next);
        if (ret > dp[aPos + 1][bPos + 1] + (a[aPos] == b[bPos] ? 0 : 5)) {
            ret = dp[aPos + 1][bPos + 1] + (a[aPos] == b[bPos] ? 0 : 5);
            nex = Next(aPos + 1, bPos + 1, -1, -1);
        }
    }

    // delete
    for (int aStart = aPos + 1; aStart <= aLen; ++aStart) {
        int cost = 9 + 2 * (aStart - aPos - 1);
        rec(aStart, bPos, dp, next);
        if (ret > cost + dp[aStart][bPos]) {
            ret = cost + dp[aStart][bPos];
            nex = Next(aStart, bPos, aStart, -1);
        }
    }
    
    // insert
    for (int bStart = bPos + 1; bStart <= bLen; ++bStart) {
        int cost = 9 + 2 * (bStart - bPos - 1);
        rec(aPos, bStart, dp, next);
        if (ret > cost + dp[aPos][bStart]) {
            ret = cost + dp[aPos][bStart];
            nex = Next(aPos, bStart, -1, bStart);
        }
    }
}


void work() {
    static int dp[BUF][BUF];
    static Next next[BUF][BUF];
    memset(dp, -1, sizeof(dp));
    rec(0, 0, dp, next);
    
    cout << dp[0][0] << endl;
    
    int aPos = 0;
    int bPos = 0;
    string aAns;
    string bAns;
    while (!(aPos == aLen && bPos == bLen)) {
        Next &nex = next[aPos][bPos];

        // match
        if (nex.aStart == -1 && nex.bStart == -1) {
            aAns += a[aPos];
            bAns += b[bPos];
        }
        // delete
        else if (nex.aStart != -1) {
            for (int i = aPos; i < nex.aStart; ++i) {
                aAns += a[i];
                bAns += '-';
            }
        }
        // insert
        else {
            for (int i = bPos; i < nex.bStart; ++i) {
                aAns += '-';
                bAns += b[i];
            }
        }
        aPos = nex.aPos;
        bPos = nex.bPos;
    }

    cout << aAns << endl;
    cout << bAns << endl;
}


int main() {
    read();
    work();
    return 0;
}
0