在线编程在线课堂在线测评Anycodes在线编程

编程论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

How to use bs4??
本帖最后由 carry0987 于
Double Queue 问题描述 : The new founded Balkan Investment Group Bank (
John 问题描述 : Little John is playing very funny game
linux-command Linux命令大全搜索工具,内容包含Linux命令
Coati 是一款跨平台的代码查看工具,适用于 C/C++ 和 Java。商业软件。特性:1. 索引
系统可承载海量并发,消息收发确认机制 保障消息必达 系统采用动态智
全平台视频监控,支持安卓苹果以及pcweb,支持海康大华等主流dvr,全部源码以及文档 单聊、群聊、商
如何访问类的私有属性? 下面以 TPathData 为例,
问题:从 XE4 以来,Firemonkey 曲线绘图在移动平台不平滑的问题一直令人诟病,提交到官方的 QC 也是族繁不及备载,官方似乎有意的
操作数据库(RODBC)   odbcConnect(dsn, uid="", p
数据模式:mode函数显示任何对象的模式。常见的单个的
系统可承载海量并发,消息收发确认机制 保障消息必达 系统采用动态智
RabbitMQ与PHP(一) 项
Iease团队扩编预备中,盼望能有Ruby或者java工程师加盟。全职兼职都可以。有爱好的伴侣请与我接洽。 邮件:i
ruby 怎么设置装备摆设GTK2,求教指导下!
#include #include #include #include using namespace std; int main() {
标题如图所示: 有n盏灯,编号1~n。一开端灯都是关着的
成熟的消息收发确认机制,支持万人大群 支持开发自定义的消息sdk接口,扩展性超强 支持单/
成熟的消息收发确认机制,支持万人大群 支持开发自定义的消息sdk接口,扩展性超强 支持单/
1. 注意列表和集合的区别 set 列表表现形式: list_1
Ajax   Ajax即“Asynchronous Javascript And
大师好,我比来在做布谷鸟优
分辨提取A和B图像Harris角点,接下来须要对

[HDU杭电] HDU 1294 Rooted Trees Problem-动态规划-[解题报告] C++

[复制链接]
发表于 2016-3-26 22:17:52 | 显示全部楼层 |阅读模式
Rooted Trees Problem


问题描述 :
Give you two definitions tree and rooted tree. An undirected connected graph without cycles is called a tree. A tree is called rooted if it has a distinguished vertex r called the root. Your task is to make a program to calculate the number of rooted trees with n vertices denoted as Tn. The case n=5 is shown in Fig. 1.

HDU 1294 Rooted Trees Problem-动态规划-[解题报告] C++

HDU 1294 Rooted Trees Problem-动态规划-[解题报告] C++

输入:
There are multiple cases in this problem and ended by the EOF. In each case, there is only one integer means n(1<=n<=40) .
输出:
For each test case, there is only one integer means Tn.
样例输入:

  1. 1
  2. 2
  3. 5
复制代码
样例输出:

  1. 1
  2. 1
  3. 9
复制代码
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7. #define LL __int64
  8. const LL maxn=44;
  9. LL dp[maxn]={0,1,1,2,4,9,20,48,115,286,719,1842,4766,12486,32973,87811,235381,634847,1721159,4688676,
  10.                 12826228,35221832,97055181,268282855,743724984,2067174645,5759636510,16083734329,
  11.                 45007066269,126186554308,354426847597,997171512998,2809934352700,7929819784355,
  12.                 22409533673568,63411730258053,179655930440464,509588049810620,1447023384581029,
  13.                 4113254119923150,11703780079612453};//可以直接打表了。。
  14. LL e[maxn],t,s;
  15. LL C(LL n,LL m)//求组合数
  16. {
  17.     m=min(m,n-m);
  18.     LL i,s=1;
  19.     for(i=1;i<=m;i&#43;&#43;)
  20.         s=s*(n-i&#43;1)/i;
  21.     return s;
  22. }
  23. void dfs(LL a,LL step,LL num,LL sum)
  24. {
  25.     LL i,j,k;
  26.     if(sum>num)return;
  27.     if(sum==num)
  28.     {
  29.         LL s=1;
  30.         k=1;
  31.         for(i=1;i<step;i&#43;&#43;)
  32.         {
  33.             if(e[i]!=e[i-1])
  34.             {
  35.                 s*=C(dp[e[i-1]]&#43;k-1,k);
  36.                 k=0;
  37.             }
  38.             k&#43;&#43;;
  39.         }
  40.         s*=C(dp[e[step-1]]&#43;k-1,k);
  41.         dp[num&#43;1]&#43;=s;
  42.         return;
  43.     }
  44.     for(i=a;i<=num;i&#43;&#43;)
  45.     {
  46.         e[step]=i;
  47.         dfs(i,step&#43;1,num,sum&#43;i);
  48.     }
  49. }
  50. void init()
  51. {
  52.     dp[1]=dp[2]=1;
  53.     LL i,j,k;
  54.     for(i=3;i<=40;i&#43;&#43;)
  55.     {
  56.         dp[i]=0;
  57.         dfs(1,0,i-1,0);
  58.     }
  59. }
  60. int main()
  61. {
  62.     init();
  63.     LL n;
  64.     while(cin>>n)
  65.     {
  66.         cout<<dp[n]<<endl;
  67.     }
  68.     return 0;
  69. }
  70. /*
  71.     可重复选择的组合。有n个元素,每个元素可以选多次,一共选k个袁术,有多少种选择?
  72.     n=3,k=2,有6种:(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)
  73.     共 C(k&#43;n-1,n-1)=C(n&#43;k-1,k)种

  74.     本题,求n个结点数的树有多少种,可采用整数划分n-1的方法
  75.     n=5时,划分4=1&#43;1&#43;1&#43;1=1&#43;1&#43;2=1&#43;3=2&#43;2=4。
  76.     则dp[5]=C(dp[1]&#43;4-1,4)&#43;C(dp[1]&#43;2-1,2)*dp[2]&#43;dp[1]*dp[3]&#43;dp[2]*dp[2]&#43;dp[4]=9;

  77. */
复制代码
在线编程(http://www.anycodes.cn)&编程论坛(http://www.52exe.cn)感谢您的支持!
回复

使用道具 举报

发布主题 上个主题 下个主题 快速回复 返回列表 官方QQ群
在线客服
客 服 中 心
群 机 器 人
网站二维码
收 起 客 服

QQ|Archiver|手机版|小黑屋|Anycodes ( ICP14002806Anycodes在线编程

GMT+8, 2018-11-15 04:47 , Processed in 1.306687 second(s), 78 queries .

Powered by Anycodes

© 2001-2013 吉林市群龙科技有限公司 Inc.

快速回复 返回顶部 返回列表