COJ 1351 Tree Counting 动态规划

题目大意是：

给定一个n，k，表示树上共有n个节点，每个节点最多有k个叶子，问一共多少种摆法，答案对1000000007取模

这里定义一个dp[i]表示 i 个节点对应有多少种方法

f[i][j] 表示一个除去顶点的树中，这个顶点延伸出 j 个子树，这j个子树中共有i 个点

那么只要在f[i][j]上添加一个顶点就得到了 dp[i]

所以dp[i+1] = f[i][0] + f[i][1] ......+f[i][k]

f[i][j] = ∑(f[i-k][j-1]*dp[k]) k<=i;

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #define maxn 205

 const int mod = ;

 using namespace std;

 long long dp[maxn],f[maxn][];

 int main()

 {

    // freopen("a.in" , "r" , stdin);

     int T,n,k;

     scanf("%d",&T);

     while(T--)

     {

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

         memset(f ,  , sizeof(f));

         memset(dp ,  , sizeof(dp));

         f[][] = ;

         dp[] = ;

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

             for(int j=k ; j>= ; j--){

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

                     f[i][j] += (f[i-t][j-]*dp[t])%mod;

                     f[i][j]%=mod;

                 }

                // cout<<"i: "<<i<<" j: "<<j<<" "<<f[i][j]<<endl;;

             }

             for(int j= ; j<=k ; j++){

                 dp[i+] += f[i][j];

                 dp[i+]%=mod;

             }

           //  cout<<"i: "<<i<<" "<<dp[i]<<endl;

         }

         printf("%lld\n" , dp[n]);

     }

     return ;

 }

巴特西

COJ 1351 Tree Counting 动态规划

最新文章

热门文章