20分求助

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

Myl100313 @ 2024-12-07 12:49:10

诸位,请看代码。

代码如下:

#include<bits/stdc++.h>
using namespace std;
const int S=114514;
int s1[S+10],s2[S+10];
int n;
int f[5002][5002];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      cin>>s1[i];
    for(int i=1;i<=n;i++)
      cin>>s2[i];
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
      {
        f[i][j]=max(f[i][j-1],f[i-1][j]);
        if(s1[i-1]==s2[j-1])
          f[i][j]=f[i-1][j-1]+1;
      }
    cout<<f[n][n]<<endl;;
    return 0;
}

数组足够大,样例可以过,20分,什么情况?谁能解释一下?谢谢。


by _WhiteDeer_ @ 2024-12-07 13:00:15

@Myl100313 O(n^2)肯定过不了啊。


by Myl100313 @ 2024-12-07 14:02:49

@WhiteDeerso?还有更好的方法吗?


by _WhiteDeer_ @ 2024-12-07 14:38:37

@Myl100313 二分优化成O(n log n)


by Myl100313 @ 2024-12-07 14:39:50

@WhiteDeer咋优化呢?


by _WhiteDeer_ @ 2024-12-07 14:55:18

@Myl100313 尝试这样考虑:

这两个序列的子序列离散化后,可观察到子序列在你选择对应的那个序列中是单调递增的,因此这个子序列是单调递增的。这个可以考虑二分,因为满足单调性。

于是我们可以去将dp_i改为记成该序列中上升子序列长度为i的上升子序列的最小末尾数值,从而完成优化。


by Myl100313 @ 2024-12-07 14:57:55

@WhiteDeer谢谢


|