[BZOJ4824][CQOI2017]老C的键盘(树形DP)
2024-08-26 01:24:37
4824: [Cqoi2017]老C的键盘
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 193 Solved: 149
[Submit][Status][Discuss]Description
老 C 是个程序员。作为一个优秀的程序员,老 C 拥有一个别具一格的键盘,据说这样可以大幅提升写程序的速度,还能让写出来的程序在某种神奇力量的驱使之下跑得非常快。小 Q 也是一个程序员。有一天他悄悄潜入了老 C 的家中,想要看看这个键盘究竟有何妙处。他发现,这个键盘共有n个按键,这n个按键虽然整齐的排成一列,但是每个键的高度却互不相同。聪明的小 Q 马上将每个键的高度用 1 ~ n 的整数表示了出来,得到一个 1 ~ n 的排列 h1, h2,..., hn 。为了回去之后可以仿造一个新键盘(新键盘每个键的高度也是一个 1 ~ n 的排列),又不要和老 C 的键盘完全一样,小 Q决定记录下若干对按键的高度关系。作为一个程序员,小 Q 当然不会随便选几对就记下来,而是选了非常有规律的一些按键对:对于 i =2,3, ... , n,小 Q 都记录下了一个字符<或者>,表示 h_[i/2] < h_i 或者h _[i/2] > h_i。于是,小 Q 得到了一个长度为n ? 1的字符串,开开心心的回家了。现在,小 Q 想知道满足他所记录的高度关系的键盘有多少个。虽然小 Q 不希望自己的键盘和老 C 的完全相同,但是完全相同也算一个满足要求的键盘。答案可能很大,你只需要告诉小 Q 答案 mod 1,000,000,007 之后的结果即可。Input
输入共 1 行,包含一个正整数 n 和一个长度为 n ? 1 的只包含<和>的字符串,分别表示键盘上按键的数量,和小 Q 记录的信息,整数和字符串之间有一个空格间隔。Output
输出共 1 行,包含一个整数,表示答案 mod 1,000,000,007后的结果。Sample Input
5 <>><Sample Output
3
共5个按键,第1个按键比第2个按键矮,第1个按键比第3个按键高,第2个按键比第4个
按键高,第2个按键比第5个按键矮。
这5个按键的高度排列可以是 2,4,1,3,5 , 3,4,1,2,5 , 3,4,2,1,5 。HINT
Source
同[BZOJ3167][P4099][HEOI2013]SAO(树形DP)
完全二叉树反而好做些,且数据开到了$O(n^4)$都能过的范围,直接套上一题的式子即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
using namespace std; const int N=,mod=;
char s[N];
int n,a[N],sum[N][N],sz[N],f[N][N],g[N],C[N][N]; void dfs(int x){
f[x][]=sum[x][]=sz[x]=;
for (int s=x<<; s<=((x<<)|); s++){
if (s>n) return; dfs(s);
memset(g,,sizeof(g));
if (a[s]==){
rep(i,,sz[x]) if (f[x][i]) rep(j,,sz[s]) if (sum[s][j])
g[i+j]=(g[i+j]+1ll*f[x][i]*sum[s][j]%mod*C[i+j-][i-]%mod*C[sz[x]-i+sz[s]-j][sz[x]-i]%mod)%mod;
}else{
rep(i,,sz[x]) if (f[x][i]) rep(j,,sz[s])
g[i+j]=(g[i+j]+1ll*f[x][i]*(sum[s][sz[s]]-sum[s][j]+mod)%mod*C[i+j-][i-]%mod*C[sz[x]-i+sz[s]-j][sz[x]-i])%mod;
}
sz[x]+=sz[s];
rep(i,,sz[x]) f[x][i]=g[i],sum[x][i]=(sum[x][i-]+g[i])%mod;
}
} int main(){
freopen("keyboard.in","r",stdin);
freopen("keyboard.out","w",stdout);
scanf("%d",&n); scanf("%s",s+);
rep(i,,n) C[i][]=;
rep(i,,n) rep(j,,n) C[i][j]=(C[i-][j-]+C[i-][j])%mod;
rep(i,,n) if (s[i-]=='<') a[i]=; else a[i]=;
dfs(); printf("%d\n",sum[][sz[]]);
return ;
}
最新文章
- 支持“ApplicationDbContext”上下文的模型已在数据库创建后发生更改
- 可以这样去理解group by和聚合函数
- View and Data API 现在支持IE11了
- python成长之路【第十七篇】:玩转jQuery
- 关于meta标签
- solr与.net系列课程(三)solr连接数据库
- 使用Gulp和Browserify创建多个绑定文件
- HTML5中的SVG
- python 数据加密以及生成token和token验证
- js运动 多数据运动 含JSON
- 09.25日记(2014年9月25日23:22:06)用java这么多年面向对象我真的懂了吗,测试先行理念会玩吗
- Understanding Abstractions of Secure Channels 的研读
- Eclipse 配置Tomcat启动参数 Java EE IDE for Web Developers. Version: Helios Service Release 2
- 经典算法题每日演练——第七题 KMP算法
- JS之DOM那些事
- VS代码生成工具ReSharper使用手册:配置快捷键(转)
- C语言第三次作业--嵌套循环
- LVM学习笔记
- centos7更改时区
- Rabbit五种消息队列学习(一) – 总述