LICS O（n*m）+前驱路径

时间：2023-03-09 16:30:47
LICS O（n*m）+前驱路径

LICS：最长公共上升子序列；

一般令f[i][j]表示a串前i位，b串以j结尾的LICS长度。于是，答案为：max(1~m)(f[n][i]);

朴素做法：O(n^3) 相等时，从1~j-1枚举最大值。

for(int i=;i<=n;i++)

  for(int j=;j<=m;j++)

  {if(a[i]!=b[j]) f[i][j]=f[i-][j];

   else if(a[i]==b[j])

    for(int k=;k<j;k++)

        if(b[k]<b[j]) f[i][j]=f[i-][k];

       }

算法时间复杂度改进思路主要从优化第三层（k）复杂度入手。

升级做法: O(n^2logn) 利用树状数组记录f[i-1][1~j-1]最大值； 数组下表记录的是b串数值。 （第一个j循环预处理，并且更新上一次的成果）需要：树状数组和离散化。

int mx[]

for(int i=;i<=n;i++)

{

 for(int j=;j<=m;j++)

 {mx[j]=query(b[j]-)//0~b[j]-1 这些数中的f最大值

 modify(b[j],f[i-][j])//将上一轮求出的f尝试更新

 }

 for(int j=;j<=m;j++)

  if(a[i]==b[j]) f[i][j]=mx[j]+;

  else f[i][j]=f[i-][j];

}

其实这样很麻烦。 复杂度中等，还需要离散化，求具体子序列还要还原。

终极做法：O(n^2) 考虑到，每次进行j循环时，i不动，a[i]的值暂时不变。所以只需边求边记录最大值即可。 直接省掉k层循环。

for(int i=;i<=n;i++)

 {

  int mx=f[i-][];

  for(int j=;j<=m;j++)

   if(a[i]!=a[j])

    f[i][j]=f[i-][j]

   else

    f[i][j]=mx+;

   if(b[j]<a[i])//j即将变成j+1，尝试更新mx（只有b[j]<a[i]才可以保证上升）

    mx=max(mx,f[i-1][j])

 }

poj 2127 至于要求具体子序列时，需要记录使之更新的前驱，即path[i][j]=某个位置bj； 因为是“以j结尾”，所以记录bj。输出时输出b[bj]；

详见代码： ai,aj记录使答案成为ans的第一个位置。 故可以直接输出b[aj];

#include<cstdio>

#include<cstdlib>

#include<iostream>

using namespace std;

const int N=;

int f[N][N],path[N][N];

int mj,mx,sum,ai,aj;

int ans[N];

int n,m;

int a[N],b[N];

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

     scanf("%d",&a[i]);

    scanf("%d",&m);

    for(int i=;i<=m;i++)

     scanf("%d",&b[i]);

    for(int i=;i<=n;i++)

    {

     mx=;

     for(int j=;j<=m;j++)

     {

        f[i][j]=f[i-][j];

        path[i][j]=-;

        if(b[j]<a[i]&&f[i-][j]>mx)

        {

            mx=f[i-][j];

            mj=j;

        }

        else if(a[i]==b[j])

        {

            f[i][j]=mx+;

            path[i][j]=mj;

        }

        if(sum<f[i][j])

        {

            sum=f[i][j];

            ai=i;

            aj=j;

        }

     }

    }

    printf("%d\n",sum);

    int tmp=sum;

    while(tmp)

    {

        if(path[ai][aj]>-)

        {

            ans[tmp--]=b[aj];

            aj=path[ai][aj];

        }

        ai--;

    }

    for(int i=;i<=sum;i++)

     printf("%d ",ans[i]);

    return ;

}

纯手打。 参考：https://www.cnblogs.com/dream-wind/archive/2012/08/25/2655641.html

相关文章