problem

厚み$1, k$の黒いチョコレートと厚み$1$の白いチョコレートがある。 一番上と一番下が黒色であるように白黒のチョコレートを交互に積み高さ$l$以下にするとき、そのような積み方は何通りか。。

solution

DP。$O(l)$。

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
int main() {
    int l, k; scanf("%d%d", &l, &k);
    vector<ll> dp(l + 1);
    REP (i, l + 1) {
        if (i == 1 or i == k) dp[i] += 1;
        if (i - 2 >= 0) dp[i] += dp[i - 2];
        if (i - k - 1 >= 0) dp[i] += dp[i - k - 1];
    }
    ll result = accumulate(ALL(dp), 0ll);
    printf("%lld\n", result);
    return 0;
}