题解 P1852 【奇怪的字符串】

这道题就是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()]; } ```