結果
問題 | No.225 文字列変更(medium) |
ユーザー |
|
提出日時 | 2020-04-21 11:00:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 5,000 ms |
コード長 | 874 bytes |
コンパイル時間 | 2,466 ms |
コンパイル使用メモリ | 192,204 KB |
最終ジャッジ日時 | 2025-01-09 22:03:18 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:19:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 19 | scanf("%d%d", &n, &m); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:21:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 21 | scanf("%s%s", s, t); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>using namespace std;template<class T> inline bool chmin(T& a, const T b) {if (a > b) {a = b;return true;}return false;}const int INF = 1 << 29;// dp := 文字列sのi番目を変換して文字列tのj番目までと等しくするまでの最小操作回数int dp[1010][1010];int main(){int n, m;scanf("%d%d", &n, &m);char s[1010], t[1010];scanf("%s%s", s, t);for(int i = 0; i <= n; i++)for(int j = 0; j <= m; j++)dp[i][j] = INF;dp[0][0] = 0;for(int i = -1; i < n; i++) {for(int j = -1; j < m; j++) {if(i == -1 && j == -1) continue;if(i >= 0 && j >= 0) {if(s[i] == t[j]) chmin(dp[i+1][j+1], dp[i][j]);else chmin(dp[i+1][j+1], dp[i][j] + 1);}if(j >= 0) chmin(dp[i+1][j+1], dp[i+1][j] + 1);if(i >= 0) chmin(dp[i+1][j+1], dp[i][j+1] + 1);}}printf("%d\n", dp[n][m]);}