30分,萌新刚学LIS,求dalao帮忙一下
查看原帖
30分,萌新刚学LIS,求dalao帮忙一下
297925
OvCherryBlossomRain楼主2021/3/19 16:56

请求dalao帮忙,评测过的#1,#2,#3。

#4数据我调试过,发现是比答案少了1。但是我自己调试了一下代码,觉得没问题.....不知道错哪了。(个人感觉应该是height数组可能有问题,但是自己试过一些数据,发现都没问题。)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
int a[maxn],d[maxn],height[maxn],n;
int LIS(){
	int len = 1;
	d[1] = height[1];
	for(int i=2;i<=n;i++){
		if(height[i]>d[len]){
			d[++len] = height[i];
		}else{
			int j = lower_bound(d+1,d+len+1,height[i])-d;
			d[j] = height[i];
		}
	}
	return len;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&height[a[i]]);
	//for(int i=1;i<=n;i++) cout<<height[i]<<' ';cout<<endl;
	printf("%d",LIS());
	return 0;
}
2021/3/19 16:56
加载中...