CH
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
来源: http://www.bubuko.com/infodetail-3089918.html