题解 P1852 【奇怪的字符串】

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()];
}