SHARE
TWEET

Untitled

a guest Mar 25th, 2019 54 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.  
  5. // DCG-12
  6.  
  7. // There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time.
  8. // Given N, write a function that returns the number of unique ways you can climb the staircase.
  9. // The order of the steps matters.
  10.  
  11. // For example, if N is 4, then there are 5 unique ways:
  12.  
  13. // 1, 1, 1, 1
  14. // 2, 1, 1
  15. // 1, 2, 1
  16. // 1, 1, 2
  17. // 2, 2
  18. // What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from
  19. // a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.
  20.  
  21. // input:
  22. // 4
  23. // 2
  24. // 1 2
  25.  
  26. // output:
  27. // 5
  28.  
  29. int waysTD(int steps, vector<int> a){
  30.     if(steps == 0){
  31.         return 1;
  32.     }
  33.     int ans = 0;
  34.     for(int i=0;i<a.size();i++){
  35.         if(steps-a[i] >= 0){
  36.             ans += waysTD(steps-a[i],a);
  37.         }
  38.     }
  39.     return ans;
  40. }
  41.  
  42. int waysBU(int steps, vector<int> a){
  43.     vector<int> BU(steps+1);
  44.     BU[0]=1;
  45.     for(int i=1;i<=steps;i++){
  46.         BU[i]=0;
  47.         for(int j=0;j<a.size();j++){
  48.             if(i-a[j] >= 0){
  49.                 BU[i] += BU[i-a[j]];
  50.             }
  51.         }
  52.     }
  53.     return BU[steps];
  54. }
  55.  
  56. int main(){
  57.     freopen("ip.txt","r",stdin);
  58.     int t;
  59.     cin>>t;
  60.     while(t--){
  61.         int steps;
  62.         cin>>steps;
  63.         int n;
  64.         cin>>n;
  65.         vector<int> a(n);
  66.         for(int i=0;i<n;i++){
  67.             cin>>a[i];
  68.         }
  69.         cout<<waysTD(steps,a)<<endl;
  70.         cout<<waysBU(steps,a)<<endl;
  71.     }
  72.     return 0;
  73. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top