$CH5302$ 金字塔 区间$DP$/计数类$DP$
2024-09-02 02:36:37
Sol
f[l][r]表示l到r这段区间对应的金字塔结构种数
发现是f[l][r]是可以由比它小的区间推出来的
比如已知f[l+1][k],f[k+1][r],不难想到f[l][r]+=f[l+1][k]*f[k+1][r],if(s[l+1]==s[k]&&s[k+1]==s[r])
为什么是f[l+1][k]*f[k+1][r]呢,可以画图理解
如图,分为1,2两个部分.s[l],s[k+1],s[r]表示的是最上面的那个根结点;s[l+1],s[k]是左边子树的根结点
但是并不能直接枚举k,因为这样可能重复计数
因为当前不同的划分方式可能会得到一样的最终状态
为了避重,我们可以枚举这段区间的第一棵子树是哪一段
从而把区间分为第一棵子树与剩余的部分这两部分
可以采取区间DP的一般枚举方式(区间长度,起点,终点)
由于是树形的结构,所以也可以采用递归实现的方式(记搜)
Code
递归 Code
最新文章
- Md5 签名算法
- Vijos P1769 网络的关键边
- Codeforces Round #379 (Div. 2) 总结分享
- [CareerCup] 1.4 Replace Spaces 替换空格
- 如何在VMWare Workstation实现虚拟机与真机的文件共享
- iOS - OC 内存管理
- ios8 ios7 tableview cell 分割线左对齐
- iOS正则匹配手机号
- DOM笔记(十):JavaScript正则表达式
- DP总结 ——QPH
- 1346. Intervals of Monotonicity(dp)
- OpenGL超级宝典第5版&;&;开发环境搭建
- 服务器之间免密码ssh登陆
- 【LDA】修正 GibbsLDA++-0.2 中的两个内存问题
- Java面试题之Java基础
- Blob与Clob转字符串
- Windows在当前目录打开cmd
- vmware虚拟网络
- 【R】R语言常用函数
- centos7安装elasticsearch5.2.2