Secret of Chocolate Poles [ICPC2017アジア予選 A]

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ICPCOOC2017&pid=A

高さLのポールがある。
ここに

• 高さ1cmの黒ディスク
• 高さKcmの黒ディスク
• 高さ1cmの白ディスク

を乗せる。
以下の条件を満たすディスクの入れ方は何通りあるか？

• 最低1枚はディスクが入っている
• ディスクの高さの総和はL以下
• 最初と最後は黒ディスク
• 黒ディスクと白ディスクは交互に乗せる

解法

http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2650814&cid=ICPCOOC2017

dpで数えよう。
「dp[i][c] := icmまで積んでいて、一番上の色がc (c=0黒, c=1白)」
この場合に考えられる遷移は
dp[i][1] -> dp[i + 1][0] : 黒1cmを乗せる
dp[i][1] -> dp[i + K][0] : 黒Kcmを乗せる
dp[i][0] -> dp[i + 1][1] : 白1cmを乗せる
これで数え上げたら、後は、一番上の色が0である場合の総和を取って答え。
初期値は「dp[0][0] = 0, dp[0][1] = 1」のように元々白が乗っている場合を考える（末尾は黒である必要があるので）

typedef long long ll;
int L, K;
ll dp[201][2];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> L >> K;
 
    dp[0][1] = 1;
    rep(i, 0, L) {
        dp[i + 1][0] += dp[i][1];
        dp[i + K][0] += dp[i][1];
        dp[i + 1][1] += dp[i][0];
    }
 
    ll ans = 0;
    rep(i, 1, L + 1) ans += dp[i][0];
    cout << ans << endl;
}