UVA 1645 Count——dp

UVA 1645 Count——dp

dp【i】表示i个节点的树的情况数，那么求dp【i】时我们可以先拿出一个点作为根节点，这时还剩i-1个点，这i-1个点可以划分成数量为（i-1）/j大小为j的子树当且仅当(i-1)%j==0,而划分成大小为j的子树的情况数是dp【j】，这个在之前就求出来了，所以只需要枚举一下i和j就可以打表求结果了

#include #include #include #include #include using namespace std;const int maxn = 1010;const int mod = 1e9+7;int kase = 0, n, dp[maxn];void init() { memset(dp, 0, sizeof(dp)); dp[1] = 1; for (int i = 1; i <= 1000; i++) { for (int j = 1; j < i; j++) { if ((i-1)%j) continue; dp[i] = (dp[i]+dp[j]) % mod; } }}int main() { init(); while (~scanf("%d", &n)) printf("Case %d: %d\n", ++kase, dp[n]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。