几万年前做的 dp 题了,有亿点点水
题意简述
求一个字符串添加多少个空格距离最小
解法
求距离最小,可以考虑动规,其实这题的写法和最长公共子序列的写法类似。
我们设 \(f(i,j)\) 表示 \(a[1] \sim a[i]\) 和 \(b[1] \sim b[j]\) 的距离
不加空格的时候为 \(f(i,j)= f(i-1,j-1) + \left\vert a[i] - b[j]\right\vert)\);
在第一个串加空格为 \(f(i,j) = f(i-1,j) + k\);
在第二个串加空格为 \(f(i,j) = f(i,j-1) + k\);
然后我们可以发现,若都加空格相当于连个串都没有发生改变,所以状态不会转移;
所以
\(f(i,j)=\min( f(i-1,j-1) + \left\vert a[i] - b[j]\right\vert,min(f(i-1,j),f(i,j) = f(i,j-1))+k)\)。
代码如下:
#include<bits/stdc++.h>
using namespace std;
char s[2100],t[2100];
int dp[2100][2100];
int main()
{
int k;
scanf("%s %s %d",s+1,t+1,&k);
int n=strlen(s+1);
int m=strlen(t+1);
for(int i=0;i<=n;i++)dp[i][0]=k*i;
for(int i=0;i<=m;i++)dp[0][i]=k*i;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dp[i][j]=min(dp[i-1][j-1]+abs(s[i]-t[j]),min(dp[i-1][j],dp[i][j-1])+k);
}
}
cout<<dp[n][m]<<endl;
return 0;
}
标签:right,vert,int,题解,空格,MBLAST,SP4082,2100
From: https://www.cnblogs.com/dhrwhy/p/17790567.html