求大佬教 LCS 满分算法!!!

P1439 【模板】最长公共子序列

基地A_I @ 2019-03-12 21:10:57

求大佬教 LCS 满分算法!!!

我的代码:

#include<bits/stdc++.h>
#define maxn 1007
using namespace std;
int n,x[maxn],y[maxn];
int dp[maxn][maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&x[i]);
    for(int i=1;i<=n;++i)
        scanf("%d",&y[i]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            if(x[i] == y[j]) dp[i][j] = dp[i-1][j-1]+1;
            else dp[i][j] = max(dp[i][j-1] ,dp[i-1][j]);
        }
    printf("%d",dp[n][n]);
    return 0;
}

by Catalan1906 @ 2019-03-12 21:12:49

@基地A_I 二分优化,你这样做显然是AC不了的


by 基地A_I @ 2019-03-12 21:21:40

@Neptune_Disaster 求大佬教二分优化!


by Catalan1906 @ 2019-03-12 21:22:50

@基地A_I 其实也可以用树状数组优化……还有你数组开这么小明显是过不了的……


|