ICPC2017 Asia Regional Tsukuba A Secret of Chocolate Poles

ICPC 動的計画法

問題

黒と白の円盤を積み上げてタワーを作る。タワーは以下の条件を満たす必要がある

  • 一枚以上の円盤がある
  • 円盤の厚さの合計はl以下
  • 最も外側の円盤は黒
  • 同じ色同士の円盤が隣り合ってはいけない

黒の円盤は厚さ1またはkのどちらかを選ぶことができて、白の円盤は厚さ1だけ。
条件を満たすタワーは何通りあるか。

制約条件

l≦100, k≦10

解法

今までの厚みの和と最後に使った色以外、これまでに何を積んだかは関係ないのでそれらをキーにするDPをすればよい。
intだとオーバーフローするので気を付ける。

ソースコード

int main(){
	int l, k; cin >> l >> k;
	ll dp[110][2] = {}, ans = 0;
	dp[0][0] = 1;
	rep(i, l) rep(j, 2) if(dp[i][j]){
		dp[i + 1][j ^ 1] += dp[i][j];
		if(!j) dp[i + k][j ^ 1] += dp[i][j];
	}
	rep(i, l) ans += dp[i+1][1];
	cout << ans << endl;
	return 0;
}