1631-Bridging signals

問題（外部リンク）

1631 -- Bridging signals

実装の概要

信号が交差しないための条件は行き先の数字が単調増加することです。問題の1つ目の入力例では行き先が{4,2,6,3,1,5}となっており、できるだけ要素数が大きくなるように増加数列を作ると{2,3,5}となります。
このような増加部分列は動的計画法を利用して求めることができます。特に、蟻本にも書いてあるように二分探索と組み合わせることで効率よく計算することが可能です。

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		for(int i = 0; i < n; i++){
			int p = Integer.parseInt(br.readLine());

			int dest[] = new int[p];
			for(int j = 0; j < p; j++){
				dest[j] = Integer.parseInt(br.readLine());
			}

			System.out.println(solve(dest));
		}
	}

	static int solve(int dest[]){
		int n = dest.length;
		//dp[i] : 長さがi+1である増加部分列における最終要素の最小値
		int dp[] = new int[n];

		Arrays.fill(dp, Integer.MAX_VALUE);
		for(int i = 0; i < n; i++){
			int index = Arrays.binarySearch(dp, dest[i]);
			if(index < 0){
				index = -index - 1;
			}
			dp[index] = dest[i];
		}

		//INFじゃないものが答え
		int result = -1;
		for(int i = n - 1; i >= 0; i--){
			if(dp[i] != Integer.MAX_VALUE){
				result = i + 1;
				break;
			}
		}
		return  result;
	}

}