CODE FESTIVAL 2017 qual A,F: Squeezing Slimes

https://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_f

これは特に言うことはなくて、合成する操作が木に見えて、木の高さが本質とわかれば解けますね。

int N;
int B[MAX_N][2];
ll dp[MAX_N][2];

void solve() {
	cin >> N;
	rep(i, 1, N + 1) {
		ll a; cin >> a;
		int cnt = 0;
		while((1 << (cnt + 1)) <= a) cnt++;
		if((1 << cnt) == a) {
			B[i][0] = cnt; B[i][1] = cnt;
		}
		else {
			B[i][0] = cnt; B[i][1] = cnt + 1;
		}
	}
	rep(i, 1, N + 1)  {
		dp[i][0] = inf;
		dp[i][1] = inf;
	}
	rep(i, 1, N + 1) {
		dp[i][0] = min(dp[i - 1][0] + abs(B[i][1] - B[i - 1][0]), dp[i - 1][1] + abs(B[i][1] - B[i - 1][1]));
		dp[i][1] = min(dp[i - 1][0] + abs(B[i][0] - B[i - 1][0]), dp[i - 1][1] + abs(B[i][0] - B[i - 1][1]));
		if(B[i][0] != B[i][1]) {
			dp[i][0]++;
			dp[i][1]++;
		}
	}
	cout << min(dp[N][0] + B[N][0], dp[N][1] + B[N][1]) / 2 << "\n";
}