67 D Optical Experiment

問題

長方形の上の辺に点1,2,3,...nが順にある。
下側にも点1,2,3,...,nが順にある。

上側の点iからは色a[i]の光が出ていて、下側の点iには色b[i]の光が入っている。
一つの点に出る、または入る光は一つのみである。


どの二つの光をとっても、それらが交差するような光の集合のうち、
大きさが最大のものの、大きさを求めよ。

制約条件

  • n≦1000000
  • a[i], b[i]≦1000000

方針

上の辺のi番目から出た光が下の辺のp[i]番目に入るとする。
どの二つの光をとってもそれらが交差している、とは光の集合が数列p[i]の単調減少列になっていることに他ならない。


これは典型的なDPにより求められる。

ソースコード

int n,a[1000000],b[1000000],pos[1000001];
int dp[1000000];

void run(){
	cin>>n;
	rep(i,n)cin>>a[i];
	rep(i,n)cin>>b[i],pos[b[i]]=i;
	
	rep(i,n)a[i]=-pos[a[i]];
	
	rep(i,n)dp[i]=1e9;
	rep(i,n){
		int p=lower_bound(dp,dp+n,a[i])-dp;
		dp[p]=a[i];
	}
	cout<<lower_bound(dp,dp+n,1e9)-dp<<endl;
}