結果

問題 No.422 文字列変更 (Hard)
コンテスト
ユーザー square1001
提出日時 2020-03-05 20:31:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,065 bytes
コンパイル時間 891 ms
コンパイル使用メモリ 80,736 KB
実行使用メモリ 89,000 KB
最終ジャッジ日時 2024-10-14 02:07:27
合計ジャッジ時間 6,150 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 5 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1012345678;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, M; string S, T;
	cin >> N >> M >> S >> T;
	vector<vector<vector<int> > > dp(N + 1, vector<vector<int> >(M + 1, vector<int>(3, inf)));
	dp[0][0][0] = 0;
	for (int i = 0; i <= N; ++i) {
		for (int j = 0; j <= M; ++j) {
			if (i >= 1 && j >= 1) {
				dp[i][j][0] = min({ dp[i - 1][j - 1][0], dp[i - 1][j - 1][1], dp[i - 1][j - 1][2] }) + (S[i - 1] == T[j - 1] ? 0 : 5);
			}
			if (i >= 1) {
				dp[i][j][1] = min({ dp[i - 1][j][0] + 9, dp[i - 1][j][1] + 2, dp[i - 1][j][2] + 9 });
			}
			if (j >= 1) {
				dp[i][j][2] = min({ dp[i][j - 1][0] + 9, dp[i][j - 1][1] + 9, dp[i][j - 1][2] + 2 });
			}
		}
	}
	int res = min({ dp[N][M][0], dp[N][M][1], dp[N][M][2] });
	int cx = N, cy = M, cz = (res == dp[N][M][0] ? 0 : (res == dp[N][M][1] ? 1 : 2));
	string SA, TA;
	while (cx != 0 || cy != 0) {
		int cur = dp[cx][cy][cz];
		if (cx >= 1 && cy >= 1) {
			int tar = cur - (S[cx - 1] == T[cy - 1] ? 0 : 5);
			bool f = false;
			if (dp[cx - 1][cy - 1][0] == tar) cz = 0, f = true;
			else if (dp[cx - 1][cy - 1][1] == tar) cz = 1, f = true;
			else if (dp[cx - 1][cy - 1][2] == tar) cz = 2, f = true;
			if (f) {
				SA += S[--cx];
				TA += T[--cy];
				continue;
			}
		}
		if (cx >= 1) {
			bool f = false;
			if (dp[cx - 1][cy][0] == cur - 9) cz = 0, f = true;
			else if (dp[cx - 1][cy][1] == cur - 2) cz = 1, f = true;
			else if (dp[cx - 1][cy][2] == cur - 9) cz = 2, f = true;
			if (f) {
				SA += S[--cx];
				TA += "-";
				continue;
			}
		}
		if (cx >= 1) {
			bool f = false;
			if (dp[cx][cy - 1][0] == cur - 9) cz = 0, f = true;
			else if (dp[cx][cy - 1][1] == cur - 9) cz = 1, f = true;
			else if (dp[cx][cy - 1][2] == cur - 2) cz = 2, f = true;
			if (f) {
				SA += "-";
				TA += S[--cy];
				continue;
			}
		}
	}
	reverse(SA.begin(), SA.end());
	reverse(TA.begin(), TA.end());
	cout << res << endl;
	cout << SA << endl;
	cout << TA << endl;
	return 0;
}
0