求调(或许是LIS写错了……)
查看原帖
求调(或许是LIS写错了……)
1013142
Chizuru_Ichinose楼主2023/11/16 20:32
#include<bits/stdc++.h>
using namespace std;
const int kMax=1e5+5;
int n;
int l1[kMax],l2[kMax],Te[kMax],F[kMax],ans;
int main(){
	//Lcs--LIS
	cin>>n;
	for(int i=1;i<=n;i++) cin>>l1[i];
	for(int i=1;i<=n;i++) cin>>l2[i];
	//预处理
	for(int i=1;i<=n;i++){
		Te[i]=l1[i];
		l1[i]=i;
	}
	for(int i=1;i<=n;i++) l2[i]=Te[l2[i]];
	/*
	for(int i=1;i<=n;i++) cout<<l1[i]<<" ";
	cout<<'\n';
	for(int i=1;i<=n;i++) cout<<l2[i]<<" ";
	*/
	//LIS
	ans=0;
	for(int i=1;i<=n;i++) F[i]=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			int m=0;
			if(F[j]>m && l2[i]>=l2[j]) m=F[j];
			F[i]=m+1;
			if(F[i]>=ans) ans=F[i];
		}
	}
	cout<<ans;
	return 0;
}
2023/11/16 20:32
加载中...