結果
問題 | No.422 文字列変更 (Hard) |
ユーザー |
![]() |
提出日時 | 2016-09-09 23:34:48 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,974 bytes |
コンパイル時間 | 1,496 ms |
コンパイル使用メモリ | 163,432 KB |
実行使用メモリ | 20,224 KB |
最終ジャッジ日時 | 2024-11-17 06:36:30 |
合計ジャッジ時間 | 27,369 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 15 TLE * 1 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int INF = 1 << 30; int main() { int dp[1201][1201]; pair< int, int > pos[1201][1201]; fill_n(*dp, 1201 * 1201, INF); fill_n(*pos, 1201 * 1201, make_pair(-1, -1)); int n, m; string S, T; cin >> n >> m; cin >> S; cin >> T; for(int i = 0; i <= T.size(); i++) { dp[0][i] = (i == 0 ? 0 : 9 + 2 * (i - 1)); if(i != 0) pos[0][i] = {0, 0}; } for(int i = 0; i <= S.size(); i++) { dp[i][0] = (i == 0 ? 0 : 9 + 2 * (i - 1)); if(i != 0) pos[i][0] = {0, 0}; } for(int i = 0; i < S.size(); i++) { for(int j = 0; j < T.size(); j++) { int val = S[i] == T[j] ? dp[i][j] : dp[i][j] + 5; pair< int, int > rev = {i, j}; for(int k = j; k >= 0; k--) { int cost = dp[i + 1][k] + 9 + 2 * (j - k); if(cost < val) { val = cost; rev = {i + 1, k}; } } for(int k = i; k >= 0; k--) { int cost = dp[k][j + 1] + 9 + 2 * (i - k); if(cost < val) { val = cost; rev = {k, j + 1}; } } dp[i + 1][j + 1] = min(dp[i + 1][j + 1], val); pos[i + 1][j + 1] = rev; } } cout << dp[S.size()][T.size()] << endl; pair< int, int > now = {S.size(), T.size()}; string AA = "", BB = ""; while(pos[now.first][now.second].first != -1) { auto qq = pos[now.first][now.second]; if(qq.first + 1 == now.first && qq.second + 1 == now.second) { AA += S[qq.first]; BB += T[qq.second]; } else if(qq.first == now.first) { for(int j = 0; j < now.second - qq.second; j++) AA += "-"; for(int j = 0; j < now.second - qq.second; j++) BB += T[now.second - j - 1]; } else { for(int j = 0; j < now.first - qq.first; j++) BB += "-"; for(int j = 0; j < now.first - qq.first; j++) AA += S[now.first - j - 1]; } now = qq; } reverse(begin(AA), end(AA)); reverse(begin(BB), end(BB)); cout << AA << endl; cout << BB << endl; }