結果
問題 | No.225 文字列変更(medium) |
ユーザー |
![]() |
提出日時 | 2015-06-12 22:34:14 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 1,493 bytes |
コンパイル時間 | 790 ms |
コンパイル使用メモリ | 85,796 KB |
実行使用メモリ | 7,040 KB |
最終ジャッジ日時 | 2024-12-24 09:42:54 |
合計ジャッジ時間 | 1,496 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <algorithm>#include <cstdio>#include <cstdlib>#include <cctype>#include <cmath>#include <iostream>#include <queue>#include <list>#include <stack>#include <map>#include <numeric>#include <set>#include <sstream>#include <string>#include <vector>using namespace std;#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)#define rep(i,n) REP(i,0,n)#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)#define ALLOF(c) (c).begin(), (c).end()typedef long long ll;#define MAX 1000000000int solve(const string& S, const string& T){std::vector< std::vector<int> > D(S.length()+1, std::vector<int>(T.length()+1, MAX));rep(i,S.length()+1) D[i][0] = i;rep(i,T.length()+1) D[0][i] = i;REP(i,1,S.length()+1){REP(j,1,T.length()+1){int op_nop = MAX;if(S[i-1] == T[j-1]){op_nop = D[i-1][j-1];}int op_ins = MAX;if(D[i][j-1] != MAX){op_ins = D[i][j-1] + 1;}int op_del = MAX;if(D[i-1][j] != MAX){op_del = D[i-1][j] + 1;}int op_rep = MAX;if(D[i-1][j-1] != MAX){op_rep = D[i-1][j-1] + 1;}D[i][j] = min(D[i][j], op_nop);D[i][j] = min(D[i][j], op_ins);D[i][j] = min(D[i][j], op_del);D[i][j] = min(D[i][j], op_rep);}}return D[S.length()][T.length()];}int main(){int n, m;string S, T;cin >> n >> m;cin >> S;cin >> T;cout << solve(S, T) << endl;return 0;}