BZOJ3304 [Shoi2005]带限制的最长公共子序列

题面在这里

​

大力DP即可

​

示例程序：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define cl(x,y) memset(x,y,sizeof(x))
using namespace std;

const int maxn=505;
int A,B,C,f[2][maxn][maxn];
char a[maxn],b[maxn],c[maxn];
int main(){
	scanf("%s%s%s",a+1,b+1,c+1);
	A=strlen(a+1); B=strlen(b+1); C=strlen(c+1);
	for (int i=1;i<=A;i++)
	 for (int j=1;j<=B;j++)
	  if (a[i]==b[j]) f[0][i][j]=f[0][i-1][j-1]+1;
	  else f[0][i][j]=max(f[0][i-1][j],f[0][i][j-1]);
	for (int k=1;k<=C;k++){
		cl(f[k&1],192);
		for (int i=1;i<=A;i++)
		 for (int j=1;j<=B;j++){
			if (a[i]==b[j])
				if (a[i]==c[k]) f[k&1][i][j]=f[k&1^1][i-1][j-1]+1;
				else f[k&1][i][j]=f[k&1][i-1][j-1]+1;
			else f[k&1][i][j]=max(f[k&1][i-1][j],f[k&1][i][j-1]);
		}
	}
	if (f[C&1][A][B]<0) puts("NO SOLUTION");else
	printf("%d",f[C&1][A][B]);
	return 0;
}