結果
問題 | No.225 文字列変更(medium) |
ユーザー |
![]() |
提出日時 | 2020-03-29 16:59:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 5,000 ms |
コード長 | 947 bytes |
コンパイル時間 | 879 ms |
コンパイル使用メモリ | 64,412 KB |
実行使用メモリ | 7,572 KB |
最終ジャッジ日時 | 2025-01-02 15:23:18 |
合計ジャッジ時間 | 1,758 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int INF = 1<<29; // enough large value// inputint n, m;string S, T;// DP tableint dp[1010][1010];int main() {cin >> n >> m >> S >> T;// initializefor (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] has been already consideredif (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;}