AOJ0157 Russian Dolls

問題リンク Russian Dolls

• 解法

人形を頂点としたとき、人形iの中に人形jを入れることができるならばiからjへ有向辺を引きます。マトリョーシカの性質から、閉路ができることはあり得ません。するとこれは DAGになります。このグラフ上のパスの長さがすなわちマトリョーシカの値になります。DAGは末尾の頂点から更新することで効率的に最長パスが求められます。が、このとき自分は未熟だったので2乗オーダで求めています。

• ソース

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

//Russian Dolls
public class AOJ0157 {

	static class T implements Comparable<T>{
		int h,r;
		public T(int h, int r) {
			this.h = h;
			this.r = r;
		}
		public int compareTo(T o) {
			return h==o.h?r-o.r:h-o.h;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			List<T> l = new ArrayList<T>();
			for(int i=0;i<n;i++)l.add(new T(sc.nextInt(), sc.nextInt()));
			int m = sc.nextInt();
			for(int i=0;i<m;i++)l.add(new T(sc.nextInt(), sc.nextInt()));
			Collections.sort(l);
			int[] dp = new int[n+m];
			Arrays.fill(dp, 1);
			int max = 1;
			for(int i=1;i<n+m;i++){
				T a = l.get(i);
				for(int j=i-1;j>=0;j--){
					T b = l.get(j);
					if(b.h<a.h&&b.r<a.r)dp[i]=Math.max(dp[i], dp[j]+1);
				}
				max = Math.max(max, dp[i]);
			}
			System.out.println(max);
		}
	}
}