[JOYOI] 1071 LCIS

拖了好久的LCIS

f[i][j]表示a串前i个，b串以b[j]结尾的LCIS长度。

转移时考虑a[i]和b[j]是否相等，如果不等：

那么既然是以j结尾，说明a串前i-1位有一个字符和b匹配了，所以由f[i-1][j]转移来（i-1涵盖所有方案）

如果相等，那么考虑由什么转移来

f[i-1][k]是一个前驱状态，既然a[i]匹配了，就只能考虑前i-1位了，由于定义如此，所以可以“笼统地”从f[i-1][]转移来，第二维就得枚举j前面的k，且b[k]<b[j]，满足递增性质

这样做是O(n^3)的复杂度，考虑优化一下。

对于一个相等的状态，这里O(n)的转移就是优化的瓶颈了，看看怎么做。

f[i][j]只能从f[i-1][k]转移来，k还得小于j，所以可以一边循环j一边用mx记录f[i][1~j-1]的最大值，前提是b[j]>a[i]。

这样转移就可以写成f[i][j]=mx+1了，O(n^2)的复杂度。

第一维可以像01背包一样压下来，空间O(n)

#include<iostream>

#include<cstdio>

using namespace std;

const int MAXN=;

inline int rd(){

    int ret=,f=;char c;

    while(c=getchar(),!isdigit(c))f=c=='-'?-:;

    while(isdigit(c))ret=ret*+c-'',c=getchar();

    return ret*f;

}

int n;

int a[MAXN],b[MAXN];

int f[MAXN][MAXN];

int main(){

    n=rd();

    for(int i=;i<=n;i++) a[i]=rd();

    for(int i=;i<=n;i++) b[i]=rd();

    for(int i=;i<=n;i++){

        int mx=;

        for(int j=;j<=n;j++){

            if(a[i]>b[j]) mx=max(mx,f[i-][j]);

            if(a[i]!=b[j]){

                f[i][j]=f[i-][j];

                continue;

            }

            if(a[i]==b[j]) f[i][j]=mx+;

        }

    }

    int ans=;

    for(int i=;i<=n;i++) ans=max(ans,f[n][i]);

    cout<<ans;

    return ;

}

巴特西

[JOYOI] 1071 LCIS

最新文章

热门文章