Advertisement
Guest User

Untitled

a guest
Aug 2nd, 2015
231
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:640000000")
  2. #include<iostream>
  3. #include<fstream>
  4. #include<cstdio>
  5. #include<cassert>
  6. #include<cstring>
  7. #include<ctime>
  8. #include<cstdlib>
  9. #include<cmath>
  10. #include<string>
  11. #include<sstream>
  12. #include<map>
  13. #include<set>
  14. #include<queue>
  15. #include<stack>
  16. #include<vector>
  17. #include<bitset>
  18. #include<algorithm>
  19.  
  20. #define pb push_back
  21. #define ppb pop_back
  22. #define mp make_pair
  23. #define all(x) (x).begin(),(x).end()
  24. #define sz(x) (int)(x).size()
  25. #define ll long long
  26. #define bit __builtin_popcountll
  27. #define sqr(x) (x) * (x)
  28. #define forit(it,S) for(__typeof((S).begin()) it = (S).begin(); it != (S).end(); it++)
  29. #define debug(x) cout << #x <<" = " << x << endl
  30. #define forn(i, n) for(int i = 0 ; (i) < (n) ; ++i)
  31. #define printvpair(v) for(int i = 0 ; (i) < (v.size()) ; ++i) cout << v[i].first  <<" " << v[i].second << endl;
  32. #define printv(v) for(int i = 0 ; (i) < (v.size()) ; ++i) cout << v[i] << " "; cout << endl;
  33.  
  34. using namespace std;
  35.  
  36. typedef pair<int, int> pii;
  37.  
  38. const double eps = 1e-9;
  39. const double pi = acos(-1.0);
  40.  
  41. const int dx[4] = {0,  0, 1, -1};
  42. const int dy[4] = {1, -1, 0,  0};
  43.  
  44. //const int N = 100001;
  45.  
  46. int N,K;
  47. int dp[260][260][260];
  48. int solve(int n,int last,int len){
  49.     if (n == 0 && len == K + 1){
  50.         return dp[n][last][len] = 1;
  51.     }
  52.     if (dp[n][last][len] == -1){
  53.         if (len < K + 1) {
  54.             int ans = 0;
  55.             for(int i = last; i <= N; i++)
  56.                 if (i > 0 && n - i >= 0){
  57.                     ans+=solve(n - i, i,len + 1);
  58.                     debug(ans);
  59.                 }
  60.             return dp[n][last][len] = ans;
  61.         }
  62.     }
  63.     else return dp[n][last][len];
  64. }
  65. int main() {
  66.     ios_base::sync_with_stdio(0);
  67.    
  68.     memset(dp,-1,sizeof(dp));
  69.     cin >> N >> K;
  70.     int last = 0;
  71.     cout << solve(N,last,1) << endl;
  72.     return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement