1065-Wooden Sticks

問題（外部リンク）

1065 -- Wooden Sticks

実装の概要

動的計画法を用いて解きます。
それぞれの棒には長さと重さが与えられていますが、分かりやすくするためにまず長さについて昇順にソートします。これによって「前の棒よりも重さが大きいか等しいならセットアップ時間は0」と考えることができます。逆に、前の棒の方が軽いならその棒は後回しにするべき、すなわち別のグループに属する棒ということになります。
そこで、dp[i]を「i番目の棒が属するグループ」と定義します。一番シンプルなパターンは重さが単調に増加する場合で、この場合dp[i]の値は全て1となります。途中でセットアップ時間が全くかからないためです。
そうでない場合はi番目の要素がどのグループに属するべきかを考える必要があります。そのためには0～i-1番目までの全ての値（グループ番号）を確認し、もしそのときの重さよりもi番目の方が軽いならi番目のグループ番号をより大きくする必要があります。
この方法ではの時間がかかりますが十分に間に合います。

public class Main {

	public static void main(String[] args)  {
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();

		for(int i = 0; i < t; i++){
			int n = in.nextInt();

			Stick[] sticks = new Stick[n];

			for(int j = 0; j < n; j++){
				sticks[j] = new Stick(in.nextInt(), in.nextInt());
			}

			Arrays.sort(sticks);

			//dp[i] : i番目が属するグループ番号
			int dp[] = new int[n];

			int result = 0;
			for(int j = 0; j < n; j++){
				dp[j] = 1;
				for(int k = 0; k < j; k++){
					//前の要素より長さが短いか等しいにもかかわらず重さが大きい場合は別のグループとなる
					if(sticks[k].weight > sticks[j].weight){
						dp[j] = Math.max(dp[k] + 1, dp[j]);
					}
				}

				result = Math.max(dp[j], result);
			}


			System.out.println(result);
		}
	}

}

class Stick implements Comparable<Stick>{
	int length;
	int weight;

	public Stick (int l, int w){
		length = l;
		weight = w;
	}

	@Override
	public int compareTo(Stick s) {
		return this.length == s.length ? this.weight - s.weight : this.length - s.length;
	}

	public String toString(){
		return "L: "+length + " W: "+weight+" ";
	}
}