Top Down:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <iostream> #include <cstdio> #include <vector> #include <cstdlib> #define INF 1000 #define ll long long using namespace std; ll res[75][75]; int N,T,P; ll dp(int cnt,int rem) { if(cnt==1 || rem==0) return 1; if(res[cnt][rem]!=-1) return res[cnt][rem]; ll r =0; for(int i=0;i<=rem;i++) { r+= dp(cnt-1,rem-i); } res[cnt][rem]=r; return res[cnt][rem]; } int main() { int t; cin>>t; while(t--) { cin>>N>>T>>P; for(int i=0;i<75;i++) for(int j=0;j<75;j++) res[i][j]=-1; cout<<dp(N,T-N*P)<<"\n"; } return 0; } |