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; }