题解 P1852 【奇怪的字符串】
An_Account
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])。
现在上代码。
```cpp
#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()];
}
```