九野的博客,转载请注明出处:http://blog.csdn.net/acmmmm/article/details/11827257
给定字符串,求 其反向的字符串和原串的最长公共子序列
最后输出 原子串长 - 子序列长
直接开2维数组会ML,用滚动数组优化内存
#include<iostream> #include<stdio.h> #include<string> #include<string.h> #include<algorithm> #include<map> #include<list> #include<set> #include<vector> #include<queue> #include<iomanip> #include<math.h> #define N 5010 #define ll int using namespace std; inline ll Max(ll a,ll b){return a>b?a:b;} short n,dp[2][N]; char s1[N],s2[N]; int main() { int i,j; while(~scanf("%d",&n)) { scanf("%s",s1); for(i=n-1;i>=0;i--)s2[i]=s1[n-i-1]; bool cur=0; memset(dp[cur],0,sizeof(dp[cur])); for(i=0;i<n;i++) { cur^=1; dp[cur][0]=0; for(j=0;j<n;j++) if(s1[i]==s2[j]) dp[cur][j]=dp[1-cur][j-1]+1; else dp[cur][j]=Max(dp[1-cur][j],dp[cur][j-1]); } printf("%d\n",n-dp[cur][n-1]); } return 0; } /* 6 abcdbc 6 abcdcb 6 abcddb ans: 3 1 2 */