Advertisement
OIQ

Untitled

OIQ
Jan 20th, 2020
165
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. int main()
  8. {
  9.    int n, k;
  10.    cin >> n >> k;
  11.  
  12.    vector <vector<ll> > dp(n + 1, vector<ll> (2));
  13.  
  14.    if (k == 1) {
  15.     cout << 1;
  16.     return 0;
  17.    }
  18.  
  19.  
  20.    dp[1][0] = 1;
  21.    dp[1][1] = 1;
  22.  
  23.    for (int i = 2; i < k; i++) {
  24.         dp[i][0] = dp[i-1][1] + dp[i-1][0];
  25.         dp[i][1] = dp[i-1][1] + dp[i-1][0];
  26.    }
  27.  
  28.    for (int i = k; i <= n; i++) {
  29.     dp[i][0] = dp[i-1][0] + dp[i-1][1];
  30.     for (int j = i - 1; j > i - k; j--)
  31.         dp[i][1] += dp[j][0];
  32.    }
  33.  
  34.    cout << dp[n][0] + dp[n][1];
  35.  
  36.     return 0;
  37. }
Advertisement
RAW Paste Data Copied
Advertisement