Easy Tree DP?

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1487 Accepted Submission(s): 567

Problem Description

A Bear tree is a binary tree with such properties : each node has a value of 2⁰,2¹…2^(N-1)(each number used only once),and for each node ,its left subtree’s elements’ sum<its right subtree’s elements’ sum(if the node hasn’t left/right subtree ,this limitation is invalid).
You need to calculate how many Bear trees with N nodes and exactly D deeps.

Input

First a integer T(T<=5000),then T lines follow ,every line has two positive integer N,D.(1<=D<=N<=360).

Output

For each test case, print "Case #t:" first, in which t is the number of the test case starting from 1 and the number of Bear tree.(mod 10⁹+7)

Sample Input

2 2

4 3

Sample Output

Case #1: 4

Case #2: 72

Author

smxrwzdx@UESTC_Brightroar

Source

2012 Multi-University Training Contest 6

解题：哎。。连续训练了两个月，身累心更累。。不想说什么了，看这位大神的解说吧

他的钻头是可以突破天际的钻头

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 typedef long long LL;

 const LL mod = 1e9 + ;

 LL dp[maxn][maxn],c[maxn][maxn];

 void init(){

     memset(dp,-,sizeof dp);

     for(int i = ; i < maxn; ++i){

         c[i][] = c[i][i] = ;

         for(int j = ; j < i; ++j)

             c[i][j] = (c[i-][j-] + c[i-][j])%mod;

     }

 }

 LL dfs(int n,int d){

     if(n ==  && d >= ) return ;

     if(n ==  || d == ) return ;

     if(dp[n][d] != -) return dp[n][d];

     LL &ret = dp[n][d];

     ret = (dfs(n-,d-)*c[n][]*)%mod;

     for(int k = ; k <= n-; ++k)

         ret = (ret + (dfs(n-k-,d-)*dfs(k,d-)%mod*c[n-][k]%mod*c[n][])%mod)%mod;

     return ret;

 }

 int main(){

     int kase,cs = ,n,d;

     init();

     scanf("%d",&kase);

     while(kase--){

         scanf("%d%d",&n,&d);

         printf("Case #%d: %I64d\n",cs++,(dfs(n,d) - dfs(n,d-) + mod)%mod);

     }

     return ;

 }

巴特西

HDU 4359 Easy Tree DP?

Easy Tree DP?

最新文章

热门文章