mickypinata

AJJak-T002: Tiling-02

Dec 3rd, 2021
493
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5.  
  6. const int N = 30 + 5;
  7.  
  8. lli dp1[N], dp2[N];
  9.  
  10. int main(){
  11.  
  12.     int Q;
  13.     scanf("%d", &Q);
  14.     dp1[0] = 1;
  15.     dp2[1] = 1;
  16.     for(int i = 2; i <= 30; ++i){
  17.         dp1[i] = dp1[i - 2] + 2 * dp2[i - 1];
  18.         dp2[i] = dp1[i - 1] + dp2[i - 2];
  19.     }
  20.     while(Q--){
  21.         int n;
  22.         scanf("%d", &n);
  23.         cout << dp1[n] << '\n';
  24.     }
  25.  
  26.     return 0;
  27. }
  28.  
RAW Paste Data