結果
問題 | No.422 文字列変更 (Hard) |
ユーザー |
![]() |
提出日時 | 2017-04-21 15:56:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 3,000 ms |
コード長 | 2,799 bytes |
コンパイル時間 | 1,658 ms |
コンパイル使用メモリ | 177,948 KB |
実行使用メモリ | 88,832 KB |
最終ジャッジ日時 | 2024-07-20 05:03:08 |
合計ジャッジ時間 | 3,662 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 16 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,a,b) for(int i=a;i<b;i++)int N, M; string S, T;//-----------------------------------------------------------------------------------#define INF INT_MAX/2int dp[1210][1210][3];tuple<int,int,int> pre[1210][1210][3];int ord[1210][1210][3];int main() {cin >> N >> M >> S >> T;S += "#"; T += "#";rep(i, 0, N + 1) rep(j, 0, M + 1) rep(k, 0, 3) dp[i][j][k] = INF;rep(i, 0, N + 1) rep(j, 0, M + 1) rep(k, 0, 3) pre[i][j][k] = {-1, -1, -1};rep(i, 0, N + 1) rep(j, 0, M + 1) rep(k, 0, 3) ord[i][j][k] = -1;dp[0][0][0] = 0;rep(i, 0, N + 1) rep(j, 0, M + 1) rep(k, 0, 3){int d;// nothing : 3if (S[i] == T[j]) {if (dp[i][j][k] < dp[i + 1][j + 1][0]) {dp[i + 1][j + 1][0] = dp[i][j][k];pre[i + 1][j + 1][0] = {i, j, k};ord[i + 1][j + 1][0] = 3;}}// change : 0d = dp[i][j][k] + 5;if (d < dp[i + 1][j + 1][0]) {dp[i + 1][j + 1][0] = d;pre[i + 1][j + 1][0] = { i, j, k };ord[i + 1][j + 1][0] = 0;}// erase : 1d = dp[i][j][k] + 2;if (k != 1) d += 7;if (d < dp[i + 1][j][1]) {dp[i + 1][j][1] = d;pre[i + 1][j][1] = { i, j, k };ord[i + 1][j][1] = 1;}// insert : 2d = dp[i][j][k] + 2;if (k != 2) d += 7;if (d < dp[i][j + 1][2]) {dp[i][j + 1][2] = d;pre[i][j + 1][2] = { i, j, k };ord[i][j + 1][2] = 2;}}int ans = dp[N][M][0], kk = 0;rep(k, 1, 3) if (dp[N][M][k] < ans) ans = dp[N][M][k], kk = k;printf("%d\n", ans);vector<int> order;tuple<int, int, int> t = {N, M, kk};while (0 <= get<0>(t)) {int i, j, k;tie(i, j, k) = t;//printf("<%d %d %d>\n", i, j, k);order.push_back(ord[i][j][k]);t = pre[i][j][k];}order.pop_back();reverse(order.begin(), order.end());//for (int o : order) printf("%d ", o);//cout << endl;//return 0;string SS = "", TT = "";int i = 0, j = 0;for (int o : order) {if (o == 0) {assert(i <= N && j <= M);SS += S[i], i++;TT += T[j], j++;}else if(o == 1) {assert(i <= N);SS += S[i], i++;TT += "-";}else if (o == 2) {assert(j <= M);SS += "-";TT += T[j], j++;}else {assert(i <= N && j <= M);SS += S[i]; i++;TT += T[j]; j++;}}cout << SS << endl << TT << endl;}