結果
問題 | 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;}