題目鏈接 https://cn.vjudge.net/problem/UVA-1645

【題意】
輸入n（n<=1000）統計有多少個n個結點的有根樹，使得每個深度中所有結點的子結點數相同

【思路】
設答案為dp[n]，肯定要拿一個結點作為根（第0層），如果第一層只有1個結點，那么就是dp[n-1]，如果有2個結點，那么答案是dp[(n-1)/2]，以此類推，邊界是dp[1]=1

#include<bits/stdc++.h> using namespace std; typedef long long ll;const ll mod=1e9+7; const int maxn=1005;ll dp[maxn];void solve(){dp[1]=1LL;for(int i=2;i<maxn;++i){int x=i-1;for(int j=1;j<=x;++j){if(x/j*j==x) dp[i]=(dp[i]+dp[j])%mod;}} }int main(){solve();int kase=0;int n;while(scanf("%d",&n)==1 && n){printf("Case %d: %d\n",++kase,dp[n]);}return 0; }

轉載于:https://www.cnblogs.com/wafish/p/10465213.html

總結

以上是生活随笔為你收集整理的UVA 1645 - Count（简单DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。