結果
問題 | No.225 文字列変更(medium) |
ユーザー |
![]() |
提出日時 | 2021-03-30 20:47:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 5,000 ms |
コード長 | 1,265 bytes |
コンパイル時間 | 4,117 ms |
コンパイル使用メモリ | 251,496 KB |
最終ジャッジ日時 | 2025-01-20 00:57:38 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using namespace std;#define rep(i,a,b) for(int i = a; i < b; i++)#define rrep(i,a,b) for(int i = a; i >= b; i--)#define fore(i,a) for(auto& i : a)#define sz(x) (int)(x).size()#define all(x) (x).begin(),(x).end()#define rall(x) (x).rbegin(),(x).rend()using ll = long long;using pint = pair<int, int>;using pll = pair<long long, long long>;int dx[4] = {1, 0, -1, 0};int dy[4] = {0, 1, 0, -1};const int IINF = 1000100100;const long long LINF = 1LL << 60;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }int main() {int n, m; cin >> n >> m;string S, T; cin >> S >> T;vector<vector<int>> dp(n+1, vector<int>(m+1, IINF));dp[0][0] = 0;rep(i, -1, n) rep(j, -1, m) {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 (i >= 0) chmin(dp[i+1][j+1], dp[i][j+1]+1);if (j >= 0) chmin(dp[i+1][j+1], dp[i+1][j]+1);}cout << dp[n][m] << endl;return 0;}