哪位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 Leonid @ 2021-08-16 13:39:21

有看数据范围吗……


by Link_Cut_Y @ 2021-08-16 13:40:15

原来用STL lower_bound 水了过去,现在想看看DP怎么写qwq


by Link_Cut_Y @ 2021-08-16 13:40:39

1e5!!!


by Link_Cut_Y @ 2021-08-16 13:41:02

我哭了


by JRzyh @ 2021-08-16 13:42:25

@maodan12345 那不是水过去


by JRzyh @ 2021-08-16 13:42:56

二分法是这种问题的正解


by huyifei323 @ 2021-08-16 13:45:10

@maodan12345 要用long long


by Link_Cut_Y @ 2021-08-16 13:45:22

???蒟蒻表示很惊讶


by Link_Cut_Y @ 2021-08-16 13:45:49

好的谢谢dalao


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

不对啊,我已经define int long long了啊


| 下一页