CDOJ 631 敢说敢做 记忆化搜索and动规

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #include<stack>
11 #include<string>
12 
13 using namespace std;
14 
15 const long long MOD=123456781;
16 
17 long long n,k;
18 long long C[1001][1001];
19 long long dp[1001][31];
20 
21 long long dfs(long long x,long long y){
22     if (dp[x][y]!=-1) return dp[x][y];
23     if (x==0 && y==0) return 1;
24     if (x!=0 && y==0) return 0;
25     dp[x][y]=0;
26     for (long long i=1;i<=x-y+1;i++){
27             dp[x][y]=(dp[x][y]+dfs(x-i,y-1)*C[x][i]%MOD)%MOD;
28     }
29     return dp[x][y];
30 }
31 
32 int main(){
33     memset(dp,-1,sizeof(dp));
34     memset(C,0,sizeof(C));
35     for (long long i=0;i<=1000;i++) C[i][0]=1;
36     for (long long i=1;i<=1000;i++){
37             for (long long j=1;j<=1000;j++){
38                     C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
39             }
40     }
41     while (scanf("%lld%lld",&n,&k)==2){
42             printf("%lld\n",dfs(n,k));
43     }
44     return 0;
45 }
46 /*
47 1 1
48 2 2
49 */