LCS 爆 0,RE 求助

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

__a__ @ 2022-07-30 12:02:04

rt,本机样例、第一个测试点 AC,但是提交后 RE 爆 0。提交记录。

代码:

#include<cstdio>
int n,a[100001],b[100001],dp[100001][100001];
int max(int a,int b)
{
    return a>b?a:b;
}
int dfs(int x,int y)
{
    if(x<=0||y<=0)return 0;
    if(dp[x][y])return dp[x][y];
    if(a[x]==b[y])return dp[x][y]=dfs(x-1,y-1)+1;
    return dp[x][y]=max(dfs(x,y-1),dfs(x-1,y));
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    for(int i=1;i<=n;++i)scanf("%d",b+i);
    printf("%d",dfs(n,n));
    return 0;
}

大家能帮我调一下吗?谢谢!


by Dr_Gilbert @ 2022-07-30 12:14:31

@JiangZiCheng2010 您数组开得真大。而且事实上 O(n^2) 的朴素动态规划无法通过本题,要通过本题需要其他解法,可以到题解区学习。


by Hisaishi_Kanade @ 2022-07-30 12:21:33

@JiangZiCheng2010 朴素的算法不能通过


by Register_int @ 2022-07-30 12:25:25

int 开 10^10,真有你的


by irris @ 2022-07-30 12:27:21

一个一个梦飞出了天窗


|