自动搬运

查看原文

来自洛谷，原作者为

	An_Account 练习时长两年半的个人练习生

搬运于2025-08-24 21:38:52，当前版本为作者最后更新于2017-11-02 10:46:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题就是LCS的模板，状态转移方程就是dp[i][j]=(a[i-1]==b[j-1])?dp[i-1][j-1]:max(dp[i-1][j],dp[i][j-1])

其中，i代表串a已经计算到了第i个字符，j代表串b已经计算到了第j个字符，dp[i][j]代表a的前i个字符与b的前j个字符的LCS。

所以，如果这两个字符相等，那么直接继承dp[i-1][j-1]；

反之，则在dp[i-1][j]，dp[i][j-1]中选取最大的数。

为了优化一下（毕竟ab两串最大有10000个字符），所以我们可以想到滚动数组。

dp[i][j]只与上一行有关联，所以上面的那个方程可以写成if (a[i-1]==b[j-1]) dp[i%2][j]=dp[(i-1)%2][j-1]+1 else dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1])。

现在上代码。

#include <iostream>
using namespace std;
int dp[2][10001];
int main()
{
    string a,b;
    cin>>a>>b;
    for (int i=1;i<=a.size();i++)
    for (int j=1;j<=b.size();j++)
    if (a[i-1]==b[j-1]) dp[i%2][j]=dp[(i-1)%2][j-1]+1;
    else dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]);
    cout<<dp[a.size()%2][b.size()];
}