Codeforces 10 D. LCIS

問題

n項からなる数列a[i]とm項からなる数列b[i]が与えられる。
これら二つの数列に共通する（必ずしも連続しない）部分列で、かつ単調増加になっているもののうち、長さ最大のものを求めよ。

制約条件

n,m≦500

方針

DP+経路復元。

dp[i][j]を、aをちょうどi番目まで、bをちょうどj番目まで使った時の増加列の長さの最大値とする。
これを愚直に更新すると、一回の更新にO(n^2)時間がかかり、
状態の数がO(n^2)あるため、全体でO(n^4)時間かかり間に合わない。

ここで、i,jおよび次に使うaの項a[k]を一つ決めると、bの項は
j番目以降で、a[k]に等しい項のうち最初に来るものとしていいことに注目する。

aiが、bのj番目以降で最初に来るときのインデックスをpos[i][j]として、
これを前処理で全部計算しておく。
するとDPの更新がO(n)で出来るようになり、全体でO(n^3)時間で増加列を求めることができる。

ソースコード

int n,m,a[500],b[500];
int pos[501][501]; // aiがbのj番目以降で最初に現れるときのインデックス
int dp[500][500],prev[500][500];

void run()
{
	cin>>n;
	rep(i,n)cin>>a[i];
	cin>>m;
	rep(i,m)cin>>b[i];
	
	memset(pos,-1,sizeof(pos));
	
	int ans=0,ai,bi;
	rep(i,n)rep(j,m){
		if(a[i]==b[j])ans=dp[i][j]=1, ai=i, bi=j;
		else dp[i][j]=-1;
	}
	
	rep(i,n){
		int p=-1;
		for(int j=m-1;j>=0;j--){
			if(a[i]==b[j])p=j;
			pos[i][j]=p;
		}
	}
	
	rep(i,n)rep(j,m)if(dp[i][j]>0)for(int k=i+1;k<n;k++)if(a[i]<a[k]){
		int l=pos[k][j+1];
		if(l>=0&&dp[k][l]<dp[i][j]+1){
			dp[k][l]=dp[i][j]+1; prev[k][l]=i*500+j;
			if(ans<dp[k][l])ans=dp[k][l], ai=k, bi=l;
		}
	}
	
	vi res;
	rep(i,ans){
		res.pb(a[ai]);
		int nai=prev[ai][bi]/500, nbi=prev[ai][bi]%500;
		ai=nai; bi=nbi;
	}
	reverse(all(res));
	cout<<ans<<endl;
	rep(i,ans)cout<<res[i]<<(i==ans-1?"\n":" ");
}