这题就是求最长有条件的上升子序列,n很小只有500,可以承受O(n^3)
于是我们设f[i][j][k]代表第一串匹配到i,第二串匹配到j,已满足前k个条件
转移方程很好想,就不多述了
空间问题也就用滚动数组就OK了
#include<cstdio> #include<cstring> #include<iostream> #define updata(a,b) a=max(a,b) #define f(i,j,k) f[(i)&1][j][k] const int maxn=510; using namespace std; char s1[maxn],s2[maxn],s3[maxn]; int f[2][maxn][maxn]; int main(){ scanf("%s%s%s",s1+1,s2+1,s3+1); memset(f,200,sizeof(f)); int n=strlen(s1+1); int m=strlen(s2+1); int len=strlen(s3+1)+1; for (int j=0;j<=m;++j) f(0,j,0)=0; for (int i=1;i<=n;++i){ memset(f[i%2],200,sizeof(f[0])); f(i,0,0)=0; for (int j=1;j<=m;++j){ int quit=min(min(i,j),len); for (int k=0;k<quit;++k){ updata(f(i,j,k),f(i-1,j,k)); updata(f(i,j,k),f(i,j-1,k)); if (s1[i]==s2[j]){ updata(f(i,j,k),f(i-1,j-1,k)+1); if (s1[i]==s3[k+1]) updata(f(i,j,k+1),f(i-1,j-1,k)+1); } } } } if (f(n,m,len-1)<0) puts("NO SOLUTION"); else printf("%d",f(n,m,len-1)); }