【codevs 1862】LCS问题+LCS的计数
LCS的模版
#include<bits/stdc++.h>
using namespace std;
int len1,len2;
char a[5010],b[5010];
int dp[5010][5010];
int tot = 0;
int main()
{
ios::sync_with_stdio(false);
cin>>a+1>>b+1;
len1 = strlen(a+1);
len2 = strlen(b+1);
len1--,len2--;
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(a[i]==b[j])
{
dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
}
else
{
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
}
cout<<dp[len1][len2]<<endl<<tot;
return 0;
}然后这题还要统计LCS的个数。
参照一般的最长公共子序列的做法
if s1[i]==s2[j] then f[i][j]=f[i-1][j-1]+1