题目：

十分费劲地终于记录好了路径……用一个前驱。

这是 n^2 的LICS方法。其实就是 n ^ 2 log n 把“找之前的d [ j ]的max”用树状数组弄成了 n ^ 2，而这个则在每个 i 遍历 j 的时候顺便更新记录好了要用的那个值，就线性了。

j 是脚标。k 的更新有时间差，保证了“只能用脚标比自己小的”这个条件。

#include
     
      #include
      
       #include
       
        #define ll long longusing namespace std;int n,m;bool use[505][505];ll a[505],b[505],d[505],pre[2][505][505];//0是行，1是列；表示第i行与j匹配时 void print(ll cnt,ll k)                     //用了这个i吗？(和j匹配时)(use[i][j]) {                                         //上一个是？(行是0，上一行与pre[1]匹配时，以定位) //    printf("(cnt=%lld k=%lld)",cnt,k);    if(!cnt)return;    print(pre[0][cnt][k],pre[1][cnt][k]);    if(use[cnt][k])printf("%lld ",b[k]);//主要用在cnt==n时判断输出此i否 }int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);    scanf("%d",&m);    for(int i=1;i<=m;i++)scanf("%lld",&b[i]);    for(int i=1;i<=n;i++)    {        ll k=0;        for(int j=1;j<=m;j++)        //若没有选此i，行是之前的(就像d的自然copy一样)        {            if(use[i-1][j])            {                pre[0][i][j]=i-1;pre[1][i][j]=j;            }            else             {                pre[0][i][j]=pre[0][i-1][j];pre[1][i][j]=pre[1][i-1][j];            }        }        for(int j=1;j<=m;j++)        {            if(a[i]>b[j]&&d[j]>d[k])k=j;            else if(a[i]==b[j]&&d[j]
        
         mx)mx=d[i],k=i;    printf("%lld\n",mx);    print(n,k);    return 0;}
        
       
      
     

为什么这个比上一个慢？

#include
     
      #include
      
       #include
       
        #define ll long longusing namespace std;int n,m;bool use[505][505];ll a[505],b[505],d[505],pre[2][505][505];//0是行，1是列；表示第i行与j匹配时 void print(ll cnt,ll k)                     //用了这个i吗？(和j匹配时)(use[i][j]) {                                         //上一个是？(行是0，上一行与pre[1]匹配时，以定位) //    printf("(cnt=%lld k=%lld)",cnt,k);    if(!cnt)return;    print(pre[0][cnt][k],pre[1][cnt][k]);//    if(use[cnt][k])printf("%lld ",b[k]);//主要用在cnt==n时判断输出此i否     printf("%lld ",b[k]);}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);    scanf("%d",&m);    for(int i=1;i<=m;i++)scanf("%lld",&b[i]);    for(int i=1;i<=n;i++)    {        ll k=0;        for(int j=1;j<=m;j++)        //若没有选此i，行是之前的(就像d的自然copy一样)        {            if(use[i-1][j])            {                pre[0][i][j]=i-1;pre[1][i][j]=j;            }            else             {                pre[0][i][j]=pre[0][i-1][j];pre[1][i][j]=pre[1][i-1][j];            }        }        for(int j=1;j<=m;j++)        {            if(a[i]>b[j]&&d[j]>d[k])k=j;            else if(a[i]==b[j]&&d[j]
        
         mx)mx=d[i],k=i;    printf("%lld\n",mx);    if(use[n][k])print(n,k);    else print(pre[0][n][k],k);    return 0;}
        
       
      
     

 另一种记录路径的方法

#include
     
      #include
      
       #define ll long longusing namespace std;const ll INF=503;//防RE，不能大于底下的数组 ll n,m;ll a[505],b[505],d[505],pre[505][505];bool prin[505];void print(ll i,ll j){    if(!i)return;    print(i-1,pre[i][j]);    if(pre[i-1][j]!=pre[i][j]&&!prin[j])printf("%lld ",b[j]),prin[j]=1;//以防真实匹配的i的后一个非真实时的输出 //    printf("i=%d j=%d\n",i,j);            //用d的值判断比较方便，但不想开二维 }int main(){    scanf("%lld",&n);    for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);    scanf("%lld",&m);    for(ll i=1;i<=m;i++)scanf("%lld",&b[i]);    for(ll i=1;i<=n;i++)    {        ll k=0;        for(ll j=1;j<=m;j++)        {            pre[i][j]=j;            if(a[i]>b[j]&&d[j]>d[k])k=j;            else if(a[i]==b[j]&&d[j]
       
        mx)mx=d[i],k=i;    printf("%lld\n",mx);    print(n,k);}