結果
| 問題 | No.422 文字列変更 (Hard) |
| ユーザー |
 snrnsidy
|
| 提出日時 | 2021-09-20 13:46:10 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 159 ms / 3,000 ms |
| コード長 | 4,869 bytes |
| コンパイル時間 | 3,060 ms |
| コンパイル使用メモリ | 198,260 KB |
| 最終ジャッジ日時 | 2025-01-24 16:01:57 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 16 |
ソースコード
#include <bits/stdc++.h>using namespace std;int dp[1201][1201][3];int backtracking[1201][1201][3][3];int main(void){cin.tie(0);ios::sync_with_stdio(false);int n, m;string s, t;cin >> n >> m;cin >> s;cin >> t;for (int i = 0; i <= 1200; i++){for (int j = 0; j <= 1200; j++){for(int k=0;k<3;k++){dp[i][j][k] = 1e9;}}}memset(backtracking,-1,sizeof(backtracking));for(int i=1;i<=n;i++){dp[i][0][2] = 9 + 2*(i-1);backtracking[i][0][2][0] = i-1;backtracking[i][0][2][1] = 0;backtracking[i][0][2][2] = 2;}for(int i=1;i<=m;i++){dp[0][i][1] = 9 + 2*(i-1);backtracking[0][i][1][0] = 0;backtracking[0][i][1][1] = i-1;backtracking[0][i][1][2] = 1;}dp[0][0][0] = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){for(int k=0;k<3;k++){if (s[i - 1] == t[j - 1]){//dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);if(dp[i][j][0] > dp[i-1][j-1][k]){dp[i][j][0] = dp[i-1][j-1][k];backtracking[i][j][0][0] = i-1;backtracking[i][j][0][1] = j-1;backtracking[i][j][0][2] = k;}if(k==1){if(dp[i][j][1] > dp[i][j-1][k] + 2){dp[i][j][1] = dp[i][j-1][k] + 2;backtracking[i][j][1][0] = i;backtracking[i][j][1][1] = j - 1;backtracking[i][j][1][2] = k;}}else{if(dp[i][j][1] > dp[i][j-1][k] + 9){dp[i][j][1] = dp[i][j-1][k] + 9;backtracking[i][j][1][0] = i;backtracking[i][j][1][1] = j-1;backtracking[i][j][1][2] = k;}}if(k==2){if(dp[i][j][2] > dp[i-1][j][k] + 2){dp[i][j][2] = dp[i-1][j][k] + 2;backtracking[i][j][2][0] = i - 1;backtracking[i][j][2][1] = j;backtracking[i][j][2][2] = k;}}else{if(dp[i][j][2] > dp[i - 1][j][k] + 9){dp[i][j][2] = dp[i - 1][j][k] + 9;backtracking[i][j][2][0] = i - 1;backtracking[i][j][2][1] = j;backtracking[i][j][2][2] = k;}}}else{/*dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);*/if(dp[i][j][0] > dp[i-1][j-1][k] + 5){dp[i][j][0] = dp[i-1][j-1][k] + 5;backtracking[i][j][0][0] = i-1;backtracking[i][j][0][1] = j-1;backtracking[i][j][0][2] = k;}if(k==1){if(dp[i][j][1] > dp[i][j-1][k] + 2){dp[i][j][1] = dp[i][j-1][k] + 2;backtracking[i][j][1][0] = i;backtracking[i][j][1][1] = j - 1;backtracking[i][j][1][2] = k;}}else{if(dp[i][j][1] > dp[i][j-1][k] + 9){dp[i][j][1] = dp[i][j-1][k] + 9;backtracking[i][j][1][0] = i;backtracking[i][j][1][1] = j-1;backtracking[i][j][1][2] = k;}}if(k==2){if(dp[i][j][2] > dp[i-1][j][k] + 2){dp[i][j][2] = dp[i-1][j][k] + 2;backtracking[i][j][2][0] = i - 1;backtracking[i][j][2][1] = j;backtracking[i][j][2][2] = k;}}else{if(dp[i][j][2] > dp[i - 1][j][k] + 9){dp[i][j][2] = dp[i - 1][j][k] + 9;backtracking[i][j][2][0] = i - 1;backtracking[i][j][2][1] = j;backtracking[i][j][2][2] = k;}}}}}}int res = 1e9;string A,B;int idx = -1;int N = n;int M = m;for(int k=0;k<3;k++){if(dp[n][m][k] < res){res = dp[n][m][k];idx = k;}}while(1){if(N==0 && M==0){break;}if(idx==0){A = s[N-1] + A;B = t[M-1] + B;}else if(idx==1){A = '-' + A;B = t[M-1] + B;}else{A = s[N-1] + A;B = '-' + B;}int nn = backtracking[N][M][idx][0];int nm = backtracking[N][M][idx][1];int nidx = backtracking[N][M][idx][2];N = nn;M = nm;idx = nidx;}cout << res << '\n';cout << A << '\n';cout << B << '\n';return 0;}