首页 > 代码库 > USACO 2.3 Cow Pedigrees
USACO 2.3 Cow Pedigrees
Cow Pedigrees
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
INPUT FORMAT
- Line 1: Two space-separated integers, N and K.
SAMPLE INPUT (file nocows.in)
5 3
OUTPUT FORMAT
- Line 1: One single integer number representing the number of possible pedigrees MODULO 9901.
SAMPLE OUTPUT (file nocows.out)
2
OUTPUT DETAILS
Two possible pedigrees have 5 nodes and height equal to 3:
@ @ / \ / @ @ and @ @ / \ / @ @ @ @
————————————————————————题解
其实一眼就是dp啊……但是我dp弱成渣了
哎呀自己辣么久都没有刷USACO了呢……趁着国庆赶紧第二章结业吧……
其实一开始都没有想出来怎么搞,然后看别人题解说从下往上搞
好机智啊这样真的……然后就会了……
首先呢我们转移时相当于在两个子树上加一个根节点,但是相同高度节点数相同的子树再合并的话就一次
如果高度不同的话就两次,因为位置可以交换
枚举高度要花m个时间,然后就会T,所以我们记录个前缀和然后就可以秒过了
1 /* 2 ID: ivorysi 3 PROG: nocows 4 LANG: C++ 5 */ 6 7 #include <iostream> 8 #include <string.h> 9 #include <cstdlib>10 #include <cstdio>11 #include <algorithm>12 #include <cstring>13 #include <vector>14 #include <ctime>15 #include <cmath>16 #include <queue>17 #define ivorysi18 #define mo 100000000719 #define siji(i,x,y) for(int i=(x);i<=(y);i++)20 #define gongzi(j,x,y) for(int j=(x);j>=(y);j--)21 #define xiaosiji(i,x,y) for(int i=(x);i<(y);i++)22 #define sigongzi(j,x,y) for(int j=(x);j>(y);j--)23 #define ivory(i,x) for(int i=head[x];i;i=edge[i].n)24 #define pii pair<int,int>25 #define fi first26 #define se second27 #define inf 0x5f5f5f5f28 #define N 500529 typedef long long ll;30 using namespace std;31 int dp[205][105];32 int g[205][105];33 int n,m;34 int main(int argc, char const *argv[])35 {36 #ifdef ivorysi37 freopen("nocows.in","r",stdin);38 freopen("nocows.out","w",stdout);39 #else40 freopen("f1.in","r",stdin);41 #endif42 scanf("%d%d",&n,&m);43 dp[1][1]=1;44 g[1][1]=1;45 siji(i,2,m) {46 siji(j,1,n) {47 if(j+2>n) break;48 siji(k,1,n) {49 if(j+k+1>n) break;50 dp[j+k+1][i]=(1LL*dp[j+k+1][i]+1LL*dp[j][i-1]*dp[k][i-1])%9901;51 }52 }53 54 if(i-2>=1) {55 siji(j,1,n) {56 if(j+2>n) break;57 siji(k,1,n) {58 if(j+k+1>n) break;59 dp[j+k+1][i]=(1LL*dp[j+k+1][i]+1LL*dp[j][i-1]*g[k][i-2]*2)%9901;60 }61 }62 }63 siji(l,1,n) g[l][i]=(g[l][i-1]+dp[l][i])%9901;64 //一开始这句话的位置放错了,应该这一个高度算完之后再记录,否则会比较小65 }66 printf("%d\n",dp[n][m]%9901);67 return 0;68 }
USACO 2.3 Cow Pedigrees
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。