哪位dalao看看哪里错了? 老是RE

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

Link_Cut_Y @ 2021-08-16 13:38:12

#include<bits/stdc++.h>
#define int long long
#define reint register int
#define forr(i,a,b) for(reint i=(a);i<=(b);i++)
using namespace std;

const int N=2010;
int a[N];
int b[N];
int f[N][N];

bool digit(char x)
{
    return (x>='0' && x<='9');
}
inline int read()
{
    int x=0;
    int f=1;
    char ch=getchar();
    while(!digit(ch))
    {
        if(ch=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    while(digit(ch))
    {
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}

signed main()
{
    int n;
    int sum=0;
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    for(int j=1;j<=n;j++)
    {
        b[j]=read();
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j])
            {
                f[i][j]=max(f[i][j],f[i-1][j-1]+1);
            }
        }
    }
    write(f[n][n]);
}

另外,有没有优化做法提供一下谢谢


by _l_l_l_l_l_ @ 2021-08-16 14:00:19

@maodan12345 开到1e5MLE...


by Link_Cut_Y @ 2021-08-16 14:00:38

@十里 开滚动数组应该可以


by Link_Cut_Y @ 2021-08-16 14:00:51

我试一试吧


by Link_Cut_Y @ 2021-08-16 14:01:43

@WenZKbb dalao有什么优化方法吗?


by _l_l_l_l_l_ @ 2021-08-16 14:04:29

@maodan12345 可以看一眼 https://www.luogu.com.cn/blog/WenZKbb/LCS-Onlogn-note


by Link_Cut_Y @ 2021-08-16 14:39:15

感谢dalao我懂了


上一页 |