[TIOJ] 1385. 芳佳的打工

題目連結:http://tioj.infor.org/problems/1385
本題有空白!!!裸的Edit Distance題,不過要注意要吃一整行,不要只讀一段進來,不然會WA。稍微解釋一下DP式,$dp[i][j]$代表用a的前i個字元轉換成b的前j個字元所需的最少次數,那轉移就會是$dp[i][j] = \begin{cases} dp[i-1][j-1],& \text{if } a[i-1] = b[j-1]\\ \min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1, & \text{otherwise} \end{cases}$,因為如果$a[i]==b[j]$那顯然不需要作修改,而若不同,則看看用插入、刪除或取代哪個比較好。
#include <bits/stdc++.h>
using namespace std;

const int N = 1000 + 5;

int dp[N][N];

int main(){
	string a, b;
	getline(cin, a);
	getline(cin, b);
	int lenA=a.size(), lenB=b.size();
	for(int i=0;i<=lenA;i++) dp[i][0] = i;
	for(int i=0;i<=lenB;i++) dp[0][i] = i;
	for(int i=1;i<=lenA;i++){
		for(int j=1;j<=lenB;j++){
			if(a[i-1] == b[j-1])
				dp[i][j] = dp[i-1][j-1];
			else
				dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]})+1;
		}
	}
	cout<<dp[lenA][lenB]<<'\n';
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology