求助90分,第二个测试点错误?为啥

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

elpsconr @ 2024-05-23 23:19:35

不知道为啥第二个测试点出问题

#include <bits/stdc++.h>
using namespace std;
const int MAXX=100000+5;
const int INF=INT_MAX;

int dp[MAXX];
int a[MAXX],b[MAXX];

int main()
{
    int n;
    cin>>n;
        int v;
        for(int i=0; i<n; i++)
        {
            cin>>v;
            a[v]=i;//把a[i]映射到i
        }
        for(int i=0; i<n; i++)
        {
            cin>>v;
            b[i]=a[v];//把b数组按照a数组的映射规则进行映射
        }
       // for(int i=0; i<n; i++)
           // dp[i]=INF; //初始化

        int pos=0;    // 记录dp当前最后一位的下标
        //dp[0]=b[0];
        for(int i=0; i<n; i++)
        {
            if(b[i]>dp[pos])
                dp[++pos]=b[i];
            else
                dp[lower_bound(dp,dp+pos+1,b[i])-dp]=b[i];
        }
        //if(pos!=99999) 
        cout<<pos<<endl;
        //else cout<<100000<<endl;
    return 0;
}

by elpsconr @ 2024-05-23 23:20:27

把dp[0]初始化成b[0]就可以ac不知道为啥


by dingyyds11111 @ 2024-05-24 00:09:12

@elpsconr 我觉得肯定要初始化啊,就相当于将LCS转换成LIS,LIS就是这样的


by dingyyds11111 @ 2024-05-24 00:12:14

@elpsconr 你pos没加1


by XICHENCHEN @ 2024-06-27 18:02:53

试试这个数据

5

1 2 3 4 5

1 2 3 4 5


by XICHENCHEN @ 2024-06-27 18:04:44

可以映射为1~n,如果从0开始会出现问题


by XICHENCHEN @ 2024-06-27 18:08:02

如果两组数据第一个数相同,结果就会-1


|