ICPCアジア地区つくば大会2017 A問題 : Secret of Chocolate Poles

問題. Secret of Chocolate Poles

厚さが1cmの白と黒の薄いチョコレートと，厚さが $k$ cmの黒の厚いチョコレートの3種類がある．高さ $l$ cm 以内で黒色と白色が交互に配置されるチョコレートの積み重ね方が何通りあるか求めよ．ただし，一番下と一番上の色は黒とする．

制約： $1 \le l \le 200$ ，　 $2 \le k \le 10$

高さがちょうど $h$ cmとなるチョコレートの積み重ね方の数を $P_h$ とする．このとき，各 $i \,(1 \le i \le l)$ に対して， $P_i = P_{i - 2} + P_{i - k - 1}$ となる．ただし， $i \le 0$ のとき $P_i = 0$ ， $P_1 = 1$ ， $k \le l$ のとき $P_k = 1$ とする．後は，この漸化式を計算して $\sum_{i =1}^{l} P_i$ を答えとする．

計算時間： $O(l)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

class SecretOfChocolatePoles {
public:
    SecretOfChocolatePoles(int l, int k) : l(l), k(k), dp(l + 1) {};

    long long Count() {
        dp[1] = 1;
        if (k <= l) dp[k] = 1;
        for (int h = 2; h <= l; ++h) {
            if (0 <= h - 2) dp[h] += dp[h - 2];
            if (0 <= h - k - 1) dp[h] += dp[h - k - 1];
        }

        return accumulate(dp.begin(), dp.end(), 0LL);
    }
private:
    int l, k;
    vector<long long> dp;
};

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

   int l, k;
   cin >> l >> k;
   SecretOfChocolatePoles scp(l, k);
   cout << scp.Count() << '\n';

    return 0;
}