关键词：
一个深度为i的树可以由一个根节点外加两个深度为i-1的树组成，这就决定了DP该怎么写。
然而我真的没有想到。
f[i][j]表示深度为i节点数为j的个数
sum[i][j]表示深度小于等于i节点树为j的个数
#include <cstdio>
#define N 402
#define p 9901
int n, m;
int f[N][N], sum[N][N];
//f[i][j]表示深度为i节点数为j的个数
//sum[i][j]表示深度<=i节点数为j的树的个数
int main()
{
int i, j, k;
scanf("%d %d", &n, &m);
if(!(n & 1))
{
puts("0");
return 0;
}
f[1][1] = sum[1][1] = 1;
for(i = 2; i <= m; i++)
{
//两个深度都是i-1
for(j = 1; j <= n; j++)
for(k = 1; k <= n; k++)
f[i][1 + j + k] = (f[i][1 + j + k] + f[i - 1][j] * f[i - 1][k] % p) % p;
//一个深度为i-1
for(j = 1; j <= n; j++)
for(k = 1; k <= n; k++)
f[i][1 + j + k] = (f[i][1 + j + k] + f[i - 1][j] * sum[i - 2][k] * 2 % p) % p;
//更新sum
for(j = 1; j <= n; j++)
sum[i][j] = (sum[i - 1][j] + f[i][j]) % p;
}
printf("%d
", f[m][n]);
return 0;
}
luogu1472奶牛家谱cowpedigrees[动态规划](代码片段)
一时暴搜一时爽一直暴搜一直爽 cxl居然和我写的同款dfs，天呢菜鸡开始对这题并没有什么想法状态方程死活想不出来还是暴搜好1#include<bits/stdc++.h>2usingnamespacestd;3#definelllonglong4#definergregister5constintN=200,K=100,P=9901;6intn,k,f[K+5... 查看详情
奶牛家谱cowpedigrees(代码片段)
令人窒息的奶牛题题目描述农民约翰准备购买一群新奶牛。在这个新的奶牛群中,每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3<=N<200)。这些二叉树有如下性质:每一个... 查看详情
luogup2345奶牛集会
二次联通门: luoguP2345奶牛集会 /*luoguP2345奶牛集会权值线段树以坐标为下标，坐标为值建立线段树对奶牛按听力由小到大排序对于要查的牛每次第i次放入奶牛起作用的v就是vi； 每次ans+=（xi*sum-sumxl）*vi+（... 查看详情
luogup2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没... 查看详情
luogup1154奶牛分厩[数论]
题目描述农夫约翰有Ｎ（1<=Ｎ<=5000）头奶牛，每头奶牛都有一个唯一的不同于其它奶牛的编号Ｓi，所有的奶牛都睡在一个有Ｋ个厩的谷仓中，厩的编号为０到Ｋ－１。每头奶牛都知道自己该睡在哪一个厩中，因为约翰教会... 查看详情
美国血统
【题目描述】农夫约翰把他的奶牛们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而不是用图形的方法。你的任务是在被给予奶牛家谱的“树中序遍历”和... 查看详情
[luogup1578]奶牛浴场（dp）
传送门 O(s2)算法详见论文 王知昆--浅谈用极大化思想解决最大子矩形问题我就复制你能把我怎么样QAQ#include<cstdio>#include<iostream>#include<algorithm>#defineN5010#definemax(x,y)((x)>(y)?(x):(y))#definemin(x,y)((x)& 查看详情
[luogup1868]饥饿的奶牛（dp）
传送门 先把所有区间按照左端点排序f[i]表示区间0~i的最优解 #include<cstdio>#include<iostream>#include<algorithm>#definemax(x,y)((x)>(y)?(x):(y))intn,v;intf[3000001];structnode{ intx,y;}p[150001]; 查看详情
luogup1824进击的奶牛
题目描述FarmerJohn建造了一个有N(2<=N<=100,000)个隔间的牛棚，这些隔间分布在一条直线上，坐标是x1,...,xN(0<=xi<=1,000,000,000)。他的C(2<=C<=N)头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛... 查看详情
luogup2344奶牛抗议(树状数组优化dp)(代码片段)
传送门 解题思路树状数组优化dp，f[i]表示前i个奶牛的分组的个数，那么很容易得出$f[i]=sumlimits_1leqjleqif[j-1]*(sum[i]gesum[j-1])$，但是这样的时间复杂度是$O(n^2)?$，所以考虑优化，发现必须满足$sum[i]gesum[j-1]?$才能进... 查看详情
题解luogup3052usaco12摩天大楼里的奶牛cowsinaskyscraper(代码片段)
迭代加深搜索基础题目描述AlittleknownfactaboutBessieandfriendsisthattheylovestairclimbingraces.Abetterknownfactisthatcowsreallydon’tlikegoingdownstairs.Soafterthecowsfinishracingtothetopoftheirfavoriteskyscr 查看详情
luogup2982[usaco10feb]慢下来slowingdown|dfs序线段树(代码片段)
题目链接 题目大意：有一棵N个结点树和N头奶牛，一开始所有奶牛都在一号结点，奶牛们将按从编号1到编号N的顺序依次前往自己的目的地，求每头奶牛在去往自己目的地的途中将会经过多少已经有奶牛的结点。 题解：... 查看详情
[luogup2915][usaco08nov]奶牛混合起来mixedupcows（dp）
传送门 f[i][S]表示当前集合为S，最后一个数为i的最优解f[i][S]+=f[j][S-i](j,i∈S&&j!=i&&abs(a[i]-a[j])>k) ——代码1#include<cstdio>2#include<iostream>3#defineLLlonglong45i 查看详情
「luogup3137」x「usaco16feb」圆形谷仓(代码片段)
#题目大意管理大大给修下$ extMarkdown$吧，严重影响做题体验啊。这道题的意思很简单就是给你一个长度是$n$的环，这个环上不均匀的分布着$n$头奶牛。一头奶牛移动要花费的代价是距离的平方，现在让你求出使得每个点上都有一... 查看详情
[luogup2858][usaco06feb]奶牛零食treatsforthecows（dp）
传送门 f[i][j][k]表示左右两段取到i....j时，取k次的最优解可以优化k其实等于n-j+i则f[i][j]=max(f[i+1][j]+a[i]*(n-j+i),f[i][j-1]+a[j]*(n-j+i))边界f[i][i]=a[i]*n递推顺序不好求，所以选择记忆化搜索。 ——代码1#include<cstdio>2#incl 查看详情
洛谷p1827美国血统americanheritagelabel：字符串water
题目描述农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而不是... 查看详情
codevs2038香甜的黄油x+luogup1828x
题目描述Description农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。农夫John很... 查看详情
luogup2925干草出售0-1背包问题(代码片段)
LuoguP2925干草出售一、题目二、参考代码2.1二维dp2.2一维dp一、题目农民john面临一个很可怕的事实，因为防范失措他存储的所有稻草给澳大利亚蟑螂吃光了，他将面临没有稻草喂养奶牛的局面。在奶牛断粮之前，john拉着他的马车... 查看详情