Advertisement
What_Ever

Untitled

Feb 18th, 2016
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.64 KB | None | 0 0
  1. #include <iostream>
  2. #include <strings.h>
  3. #include <math.h>
  4. #include <vector>
  5. #include <map>
  6. #include <utility>
  7. #include <ctype.h>
  8. using namespace std;
  9. vector <int> dp;
  10. int n , a , b , c ;
  11. int cut_ribbon(int rem )
  12. {
  13.     if(rem == 0)
  14.     {
  15.         return 0;
  16.     }
  17.     if(rem<0)
  18.         return -100000;
  19.     if(dp[rem]!=-1)
  20.     {
  21.        return dp[rem];
  22.     }
  23.     int cut1 = cut_ribbon(rem-a);
  24.     int cut2 = cut_ribbon(rem-b);
  25.     int cut3 = cut_ribbon(rem-c);
  26.     return dp[rem] = max(cut1, max (cut2 , cut3) )+1;
  27. }
  28. int main()
  29. {
  30.     cin>>n>>a>>b>>c;
  31.     dp = vector<int> (4001 , -1);
  32.     cout<<cut_ribbon(n);
  33.     return 0;
  34. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement