哪位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 Link_Cut_Y @ 2021-08-16 13:47:23

@huyifei323


by huyifei323 @ 2021-08-16 13:50:59

@maodan12345 建议直接用long long或#define ll long long,不要#define int long long,#define int long long会导致int main()时变成long long main()从而导致RE


by Link_Cut_Y @ 2021-08-16 13:56:26

@huyifei323 但是我用signed main了啊


by Link_Cut_Y @ 2021-08-16 13:56:56

楼上dalao说二分法才能过


by Sliarae @ 2021-08-16 13:57:13

@huyifei323 RE是应为数组开小了吧


by _l_l_l_l_l_ @ 2021-08-16 13:58:50

@maodan12345 二分?我记得是转换成LIS

https://www.luogu.com.cn/blog/WenZKbb/LCS-Onlogn-note


by Link_Cut_Y @ 2021-08-16 13:58:52

@十里 应该开到1e5


by _l_l_l_l_l_ @ 2021-08-16 13:59:34

@maodan12345 这题O(n^2)不行


by Sliarae @ 2021-08-16 13:59:51

@maodan12345 这题数据量有 10^5,直接开二维数组会导致 MLE 或 RE,试试其它做法吧


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

lower_bound 就是二分吧


上一页 | 下一页