[luogu] P1279 字串距离 未知条件+线性DP

前言

好难啊 传送门 :

思路

假设我们已经知道 第一个子串的前 i i i位,和第二个子串的前 j j j位

那么对于我们放进去的第 j + 1 j+1 j+1个数 只有两种情况

• 放空格
• 对应第 i i i位数

因此通过线性DP 可得以下方程 f [ i ] [ j ] = m i n f [ i − 1 ] [ j ] + k , f [ i ] [ j − 1 ] + k , f [ i − 1 ] [ j − 1 ] + a b s ( ( i n t ) s 1 [ i ] − ( i n t ) s 2 [ j ] ) ; f[i][j]=min{f[i-1][j]+k,f[i][j-1]+k,f[i-1][j-1]+abs((int)s1[i]-(int)s2[j])}; f[i][j]=minf[i−1][j]+k,f[i][j−1]+k,f[i−1][j−1]+abs((int)s1[i]−(int)s2[j]);

CODE

void solve()
{
	cin>>s1>>s2;
	cin>>k;
	int len1  = s1.size();
	int len2  = s2.size();
	
	s1 = " "+s1;
	s2 = " "+s2;
	 
	for(int i = 1 ;i