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