結果
問題 | No.225 文字列変更(medium) |
ユーザー |
|
提出日時 | 2020-07-28 05:56:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 889 bytes |
コンパイル時間 | 590 ms |
コンパイル使用メモリ | 68,292 KB |
実行使用メモリ | 7,552 KB |
最終ジャッジ日時 | 2024-06-28 20:32:00 |
合計ジャッジ時間 | 1,388 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int INF = 1<<29; // 十分大きい値にする// 入力int n, m;string S, T;// DP テーブルint dp[1010][1010];int main() {cin >> n >> m >> S >> T;// 初期化for (int i = 0; i < 1010; ++i) for (int j = 0; j < 1010; ++j) dp[i][j] = INF;dp[0][0] = 0;for (int i = -1; i < (int)S.size(); ++i) {for (int j = -1; j < (int)T.size(); ++j) {if (i == -1 && j == -1) continue; // dp[0][0] は考慮済if (i >= 0 && j >= 0) {if (S[i] == T[j]) dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]);else dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + 1);}if (i >= 0) dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j+1] + 1);if (j >= 0) dp[i+1][j+1] = min(dp[i+1][j+1], dp[i+1][j] + 1);}}cout << dp[S.size()][T.size()] << endl;}