Advertisement
Guest User

Untitled

a guest
Mar 25th, 2019
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.29 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement