dalao求助 为什么不初始化就只有20分

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

违规用户名59285 @ 2019-08-27 22:48:01


#include<cstdio>
#include<algorithm>
using namespace std;

int N;
int m[100005],a[100005],b[100005];
int l,r,mid;
int k[100005];
int cnt;
const int INF=0x3ffffff;

int main()
{
    scanf("%d",&N);
      for(int i=1;i<=N;i++)
      {
        scanf("%d",&a[i]);
        m[a[i]]=i;

      }
      for(int i=1;i<=N;i++)
      {
        scanf("%d",&b[i]);
        k[i]=INF;
      }

    k[0]=0;  
    for(int i=1;i<=N;i++)
      {
         if(m[b[i]]>k[cnt])
           {
            cnt++;
            k[cnt]=m[b[i]];         
           } 
         else
           {
             l=0;
             r=N;
             while(l<r)
               {
                 mid=(l+r)>>1;
                 if(k[mid]<m[b[i]])
                   l=mid+1;
                 else
                   r=mid;

               }
             k[l]=min(k[l],m[b[i]]);  

           }   

      }
    printf("%d",cnt);
    return 0;       
}

//这是ac代码 但去掉正无穷的初始化只有20 k[i]数组记录的是长度为k的lis的最小末尾数,但明明每次与m[b[i]]进行比较的k[cnt]都是之前被更新过的 照理说初始化与否不会造成影响啊 为什么会出错呢

by Smile_Cindy @ 2019-08-27 22:54:27

@江沢铭路

事实证明你的确用到了没被更新过的k[cnt]

虽然我不知道为什么。


by 0nullptr @ 2019-08-27 23:10:44

@江沢铭路

考虑这样的一组数据

5
1 2 3 4 5
5 1 2 3 4

那么有m[]={1,2,3,4,5}

i=1时,满足m[b[i]]>k[cnt]更新k_1=5

i=2时,不满足m[b[i]]>k[cnt]。由于l=0,r=5,所以此时mid=\lfloor( l+r)/2\rfloor=2,显然此时k_i未被使用过。因此k数组必须初始化。


by 违规用户名59285 @ 2019-08-28 17:35:29

@zs__std

噢噢 刚发现我把r=cnt写成r=N 这样的话确实如你所说 会调用到没更新的k 改成r=cnt 删掉初始化能ac 受教了


|