本文共 1013 字，大约阅读时间需要 3 分钟。

大意了啊,没有闪…

发现其实无论如何都无法避免计算$lcs$这一段…

然后觉得是$dp....$但是不会做

定义$f[i][j]$为以$a$串$i$和$b$串$j$结尾的最大贡献值

那么当$a[i]!=b[j]$时

$f[i][j]=max(0,max(f[i-1][j],f[i][j-1])-1)$

什么意思呢$?$假如从状态$(i-1,j)$或$(i,j-1)$接上来比较划算就接上来

不划算就断开,也就是取$0$

那么当$a[i]==b[j]$时

$f[i][j]=f[i-1][j-1]+2$

其实这就是基础$LCS$的思想,非常巧妙(可能是我太傻了)

#include 
   
    using namespace std;const int maxn = 5009;int n,m,ans,f[maxn][maxn];char a[maxn],b[maxn];int main(){
   	cin >> n >> m ;	cin >> (a+1) >> (b+1);	for(int i=1;i<=n;i++)	{
   		for(int j=1;j<=m;j++)		{
   			if( a[i]==b[j] )				f[i][j] = f[i-1][j-1]+2;			else				f[i][j] = max( 0,max( f[i-1][j],f[i][j-1] )-1 );			ans = max( ans,f[i][j] );		}	}	cout << ans;}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/110141601 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！