路径记录的问题

小弟不明白为什么路径记录必须要O(n2)的数组，用O(n)就是WA，
为什么

  for(i=1;i<=la;i++)
    {
    k=0;
    for(j=1;j<=lb;j++)
      {
      if (a[i]>b[j])
        if (DP[k]<DP[j])
          k=j;
      if (a[i]==b[j])
        if (DP[k]+1>DP[j])
          {
	  DP[j]=DP[k]+1;
          f[j]=k;               ------------一维路径记录
          }                    
      }  
    }
然后再从f[j]的路径中找到关于b数组的下标

为什么这个想法是错误的呢？

大牛能给出答案么？

PS:


勘误：
> 最长公共递增子序列O(n^2)模板——ZOJ2432解题报告- -
>                                        
> 
> ZOJ2432——最长公共递增子序列  WA*2  AC*4
> 
> //  时间复杂度 O(n^2), 空间复杂度 O(n^2)
> /*
>     l1为a的大小, l2为b的大小
>     结果在ans中
>     f记录路径，DP记录长度
>     用a对b扫描，逐步最优化
> */
>  
> #include<string.h>
> #include<stdio.h>
> #include<iostream.h>
>  
> #define MAXN 500
> typedef int elem_t;
>  
> int GCIS(int l1, elem_t a[], int l2, elem_t b[], elem_t ans[])
> {
>     int f[MAXN+1][MAXN+1];
>     int DP[MAXN+1];
>     int i,j,k,max;
>  
>     memset(f,0,sizeof(f));
>     memset(DP,0,sizeof(DP));
>     for (i=1;i<=l1;i++)
>     {
>         k=0;
>         memcpy(f[i],f[i-1],sizeof(f[0]));
>         for (j=1;j<=l2;j++)
>         {
>             if (b[j-1]<a[i-1] && DP[j]>DP[k]) k=j;
>             if (b[j-1]==a[i-1] && DP[k]+1>DP[j])
> 		DP[j]=DP[k]+1,f[i][j]=i*(l2+1)+k;
>         }
>     }
>     for(max=0,i=1;i<=l2;i++)
>     if (DP[i]>DP[max]) max=i;
>     for(i=l1*l2+l1+max,j=DP[max];j;i=f[i/(l2+1)][i%(l2+1)],j--)
> 	ans[j-1]=b[i%(l2+1)-1];
>     return DP[max];
> }
>  
> 
> 这题象是LIS和LCS的结合。
>  
> 能想到的最简单的方法就是对a的每一项和b的每一项进行匹配，当找到一个匹配的
> 时候，就往回找比它小的一个最长公共子列，如a[i]==b[j]，就搜a[0,i-1]*b[0,j
> -1]这个矩形里面比a[i]小的最长公共递增子列。简化的代码如下：
>  
> for(i=1;i<=l1;i++)
> for(j=1;j<=l2;j++)
> if (a[i-1]==b[j-1])
> {
>     max=0;
>     for(i1=1;i1<i;i1++)
>     for(j1=1;j1<j;j1++)
>     if (a[i1-1]==b[j1-1] && a[i1-1]<a[i-1] && f[i1][j1]>max) max=f[i1][j1];
>     f[i][j]=max+1;
> }
>  
> 这样做的效率是O(n^4)，明显是不行的。
>  
> 重新看一下上面的方法，一个最大的问题就是数组的空间没有得到重复的利用。当
> a[i]!=b[j]的时候，相应的空间就闲置了。如果能够利用闲置的空间来传递一些信
> 息，那效率就会有所提高。前面都是把a和b放在对等的地位的，现在考虑用a对b扫
> 描，然后再对得到的结果找LIS。
>  
> for(i=1;i<=l1;i++)
> for(j=1;j<=l2;j++)
> {
>     f[i][j]=a[i-1][j];

勘误1--------->个人认为是f[i][j]=f[i-1][j];


>     if (a[i-1]==b[j-1])
>     {
>         max=0;
>         for(k=1;k<j;k++)
>         if (b[k-1]<b[j-1] && f[i][max]<f[i][k]) max=k;
> /*  这里如果f[i][k]>0，因为b[k]<b[j]，所以不可能是a[i-1]和b[k]匹配，所以只
> 可能是a[0,i-2]和其匹配，故符合公共递增子列的要求    */
>         if (f[i][max]+1>f[i][j]) f[i][j]=f[i][max]+1; 
>    }
> }
>  
> 这里的复杂度是O(n^3)，但还是不行。
> 
> 考虑到匹配的时候a[i-1]==b[j-1]，可以进一步简化推出LIS的过程。
>  
> for(i=1;i<=l1;i++)
> for(j=1;j<=l2;j++)
> {
>     f[i][j]=f[i-1][j];
>     k=0;    //这里k的意义和上一个的k是一样的，注意k<=j
>     if (a[i-1]>b[j-1] && f[i][k]>f[i][j]) k=j;
>     if (a[i-1]==b[j-1] && f[i][j]<f[i][k]+1) f[i][j]=f[i][k]+1;
> }
>  
> 这段代码的复杂度为O(n^2)，加上路径记录以后就能AC 2432了。
> 

• Re:关于勘误和路径记录 ```````同问 (10) __sunshine 2009-05-11 20:45:23
  • Re:关于勘误和路径记录 ```````同问 (24) pdiibq 2009-09-16 14:48:03