前言
好难啊
传送门 :
思路
假设我们已经知道 第一个子串的前 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
关注
打赏
![]()
查看更多评论
