TopCoder SRM 667 Div1 Easy: OrderOfOperations

解法

DP.クソ.

kenkoooo.hatenablog.com

コード

import java.util.Arrays;

public class OrderOfOperations {

	public int minTime(String[] s) {
		int N = s.length;
		int M = s[0].length();

		int[] operations = new int[N];
		for (int i = 0; i < N; i++) {
			operations[i] = Integer.parseInt(s[i], 2);
		}

		int[] dp = new int[1 << M];
		Arrays.fill(dp, -1);
		dp[0] = 0;

		for (int bit = 0; bit < (1 << M); bit++) {
			if (dp[bit] < 0) {
				continue;
			}
			for (int i = 0; i < N; i++) {
				int next = operations[i] | bit;
				int k = Integer.bitCount(next ^ bit);
				int cost = k * k;// ここをMath.pow(k,2)にすると墜ちる!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
				if (dp[next] < 0) {
					dp[next] = dp[bit] + cost;
				} else {
					dp[next] = Math.min(dp[bit] + cost, dp[next]);
				}
			}
		}

		int goal = 0;
		for (int i = 0; i < N; i++) {
			goal = goal | operations[i];
		}

		return dp[goal];
	}
}