Problem 2896 --2.3.2 Cow Pedigrees

2896: 2.3.2 Cow Pedigrees

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $2$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 usaco 动态规划

Farmer John is considering purchasing a new herd of cows. In this new herd, each mother cow gives birth to two children. The relationships among the cows can easily be represented by one or more binary trees with a total of N (3 <= N < 200) nodes. The trees have these properties:

  • The degree of each node is 0 or 2. The degree is the count of the node's immediate children.
  • The height of the tree is equal to K (1 < K <100). The height is the number of nodes on the longest path from the root to any leaf; a leaf is a node with no children.

How many different possible pedigree structures are there? A pedigree is different if its tree structure differs from that of another pedigree. Output the remainder when the total number of different possible pedigrees is divided by 9901.

PROGRAM NAME: nocows

  • Line 1: Two space-separated integers, N and K. 
  • Line 1: One single integer number representing the number of possible pedigrees MODULO 9901. 
5 3
2
OUTPUT DETAILS:

Two possible pedigrees have 5 nodes and height equal to 3:
           @                   @      
          / \                 / \
         @   @      and      @   @
        / \                     / \
       @   @                   @   @

推荐代码 查看2896 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$7 $ms] 计爱玲 447984 2019-07-18 08:16:17
内存最少[$2152 $KB] 计爱玲 447984 2019-07-18 08:16:17
第一AC 计爱玲 447984 2019-07-18 08:16:17
第一挑战 计爱玲 447980 2019-07-18 07:21:42

赛题来源/所属竞赛 usaco training usaco Training

竞赛编号 竞赛名称 竞赛时间 访问比赛