[Shoi2005]帶限制的最長公共子序列

這題就是求最長有條件的上升子序列，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));
}