首页 > 代码库 > COJ 1351 Tree Counting 动态规划
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;
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define maxn 205 5 const int mod = 1000000007; 6 using namespace std; 7 8 long long dp[maxn],f[maxn][22]; 9 10 int main()11 {12 // freopen("a.in" , "r" , stdin);13 int T,n,k;14 scanf("%d",&T);15 while(T--)16 {17 scanf("%d%d" , &n , &k);18 memset(f , 0 , sizeof(f));19 memset(dp , 0 , sizeof(dp));20 f[0][0] = 1;21 dp[1] = 1;22 for(int i=1 ; i<n ; i++){23 for(int j=k ; j>=1 ; j--){24 for(int t=1 ; t<=i ; t++){25 f[i][j] += (f[i-t][j-1]*dp[t])%mod;26 f[i][j]%=mod;27 }28 // cout<<"i: "<<i<<" j: "<<j<<" "<<f[i][j]<<endl;;29 }30 31 for(int j=1 ; j<=k ; j++){32 dp[i+1] += f[i][j];33 dp[i+1]%=mod;34 }35 // cout<<"i: "<<i<<" "<<dp[i]<<endl;36 }37 printf("%lld\n" , dp[n]);38 }39 return 0;40 }
COJ 1351 Tree Counting 动态规划
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。