1631-Bridging signals

問題（外部リンク）

1631 -- Bridging signals

実装の概要

動的計画法を用いて解きます。
配線が交わらないための条件は目的地のポート番号が{1,2,4,8,,,,}のように単調増加することです。そのためこの問題は最長増加部分列（LIS）の長さを求めるのと同じ方法で解くことができます。ただし入力がp<40000となっており、dp[i]を例えば「i番目までで作れるLISの長さの」などとしてしまうととなり間に合いません。そこで、蟻本に書いてあった方法ですがdp[i]を「長さがi+1であるような増加部分列における最終要素の最小値」と定義して二分探索を用いるととなり高速化できます。
本にはC++での実装例が載っていますが、Javaでは以下のように書くことができます。

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

			//debug
//			for(int j = 0; j < n; j++){
//				System.out.print(dp[j]+" ");
//			}
//			System.out.println();
		}

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

}