結果

問題 No.422 文字列変更 (Hard)
ユーザー HachimoriHachimori
提出日時 2016-09-10 01:15:32
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,099 bytes
コンパイル時間 595 ms
コンパイル使用メモリ 58,468 KB
実行使用メモリ 21,632 KB
最終ジャッジ日時 2024-11-17 06:47:44
合計ジャッジ時間 57,642 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 TLE -
testcase_02 TLE -
testcase_03 TLE -
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 WA -
testcase_08 AC 57 ms
19,200 KB
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
権限があれば一括ダウンロードができます

ソースコード

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;
    int len;
    Next(){}
    Next(int aPos, int bPos, int aStart, int bStart, int len):
        aPos(aPos), bPos(bPos), aStart(aStart), bStart(bStart), len(len) {}
};


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) {
        ret = bLen == bPos ? 0 : 9 + 2 * (bLen - bPos - 1);
        nex = Next(aLen, bLen, -1, bLen, 0);
        return;
    }
    if (bPos == bLen) {
        ret = aLen == aPos ? 0 : 9 + 2 * (aLen - aPos - 1);
        nex = Next(aLen, bLen, aLen, -1, 0);
        return;
    }
    
    ret = INF;
    
    for (int bStart = bPos; bStart < bLen; ++bStart) {
        int cost = bStart == bPos ? 0 : 9 + 2 * (bStart - bPos - 1);
        for (int len = 1; aPos + len <= aLen && bStart + len <= bLen; ++len) {
            cost += a[aPos + len - 1] == b[bStart + len - 1] ? 0 : 5;
            rec(aPos + len, bStart + len, dp, next);
            if (ret > cost + dp[aPos + len][bStart + len]) {
                ret = cost + dp[aPos + len][bStart + len];
                nex = Next(aPos + len, bStart + len, -1, bStart, len);
            }
        }
    }

    for (int aStart = aPos; aStart < aLen; ++aStart) {
        int cost = aStart == aPos ? 0 : 9 + 2 * (aStart - aPos - 1);
        for (int len = 1; bPos + len <= bLen && aStart + len <= aLen; ++len) {
            cost += b[bPos + len - 1] == a[aStart + len - 1] ? 0 : 5;
            rec(aStart + len, bPos + len, dp, next);
            if (ret > cost + dp[aStart + len][bPos + len]) {
                ret = cost + dp[aStart + len][bPos + len];
                nex = Next(aStart + len, bPos + len, aStart, -1, len);
            }
        }
    }
}


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];

        if (nex.aStart != -1) {
            for (int i = aPos; i < nex.aStart; ++i) {
                aAns += a[i];
                bAns += '-';
            }
            aPos = nex.aStart;
        }
        for (int i = aPos; i < aPos + nex.len; ++i) {
            aAns += a[i];
        }

        if (nex.bStart != -1) {
            for (int i = bPos; i < nex.bStart; ++i) {
                aAns += '-';
                bAns += b[i];
            }
            bPos = nex.bStart;
        }
        for (int i = bPos; i < bPos + nex.len; ++i) {
            bAns += b[i];
        }

        aPos = nex.aPos;
        bPos = nex.bPos;
    }

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


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