【Luogu】P1472奶牛家谱(DP)
2024-08-29 10:18:44
这是一道考思维的好题。
一开始设f[i][j]是i个点刚好j层的方案数,死活调不出来,看题解发现可以改为<=j层的方案数,最后输出f[n][m]-f[n][m-1]就好了。
对于计算考虑左右子树分配,设i个点分给左子树,j个点分配右子树,注意枚举顺序,乘法原理搞一搞就好。
我拼尽全力只得了57分,qwq。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define mod 9901
#define maxn 250
using namespace std;
inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} int f[maxn][maxn];
int s[maxn][maxn];
int n,m; int main(){
n=read(),m=read();
for(int i=;i<=m;++i) f[][i]=;
for(int j=;j<=m;++j){
for(int i=;i<=n;++i){
int &o=f[i][j];
for(int k=;k<i-;++k) o=(o+f[k][j-]*f[i-k-][j-])%mod;
}
}
printf("%d\n",(f[n][m]-f[n][m-]+mod)%mod);
return ;
}
最新文章
- 如何清除Xcode8打印的系统日志
- RapidJson读取json文档
- DDGSpring2016 Demos
- NYOJ926(概率)
- Hive0.11安装配置学习笔记
- HDU 1695 GCD (欧拉函数+容斥原理)
- BeagleBone Black项目实训手册(大学霸内部资料)
- 表单美化-原生javascript和jQuery多选按钮(兼容IE6)
- java开发--struts2 标签库使用
- Codeforces Round #307 (Div. 2) A. GukiZ and Contest 水题
- Starting MySQL.. ERROR! The server quit without updating PID file (/usr/local/mysql/data/localhost.localdomain.pid).
- File System Shell
- 文件IO理解
- zookeeper3.4.13集群安装
- java jdk动态代理模式举例浅析
- IDEA指定.class文件输出位置
- ionic使用iframe时无法显示网页或报错
- 〖Android〗依据资源信息,Mock Android资源
- TensorFlowIO操作(三)------图像操作
- 为什么int类型的数据可以存储超过9999?
热门文章
- (转)SQL注入攻击简介
- rhythmbox插件开发笔记3:安装 makefile &;&; schema &;&; po
- spring maven 包
- spring-data-JPA源码解读
- python之道10
- Java基础面试操作题:线程同步代码块 两个客户往一个银行存钱,每人存三十次一次存一百。 模拟银行存钱功能,时时银行现金数。
- Python9-网络编程3-day32
- 给vagrant中的precise64升级VBoxGuestAdditions
- 利用http录制jmeter脚本
- SQL_4_函数