总结

冬月初三，早起，天气清冷。气温骤降，秋风瑟瑟。今天是计数类 dp，但是先来回顾一下上次的动态 dp。【模板】动态DP 动态树分治（加强版） ，两个的树剖过不了了，得使用 LCT 或者全局平衡二叉树。这里学习一下全局平衡二叉树。

全局平衡二叉树 yyds！很好的写法，OI-WIKI 上的写法好神奇，写起来好▒▒。

计数类 dp

收藏一下 alex-wei 的 dp 大杂烩（）

DP 优化方法大杂烩 I.

DP 优化方法大杂烩 II.

好文章捏，抄了。

P4590 [TJOI2018]游园会 要满足不能出现 NOI。虽然是 dp 套 dp，但应该还是算计数 dp 吧，嘻嘻。

这种有奇奇怪怪限制的计数题，从动态规划的角度切入通常比较顺手。****

接下来是来自 dzy 的计数类题目题单。

• Codeforces 17C 相当于原子序列复制。和上面 dp 套 dp 差不多，本质上都是构建自动机来转移状态，从而满足限制。比如这道题就是限制子序列，每次的转移就是字符，这道题是序列自动机，状态很简单，就是原串上的位置。P.S. 感觉这种 dp 写向后更新都比较容易啊。

• Codeforces 474D 简单的 dp 题目。

• Codeforces 486D 也不难，觉得没有蓝题的难度，但是 wa 了。你猜怎么着？我定义一个函数，模意义下取模，大于等于 mod 要减 mod 对吧，我减的 y。awsl。

• ABC104 D 倒过来乱搞一下就行，也不难。

• Codeforces 176B 容易发现就是一个字符串转，然后有一些模数。由于字符串很短，可以暴力找结束位置，然后暴力dp 即可。看题解发现可以优化。定义表示这一步到答案或不是答案的情况，转移即可。

• [ZJOI2012] 波浪 发现是黑题，害怕。难度骤增。积累经验，挖坑 dp。（自己取的名字）。此题可能需要高精度小数。但是不想打，用 __float128 淦，发现 TLE 两个点，采用数据类型分治，精度小于 8 位的使用 double。简单说明一下挖坑 dp，最开始没有理解，后来发现好厉害。就是维护一些段，每次加进去一个点相当于往一些段间加一个点进去，这个点可以把两边的段扯到一起，就像缝衣服一样，然后 dp 的时候再维护一下两边的边界就好。

• [TJOI2015] 组合数学 怎么这道题是紫题上一道是黑的啊～。参看题解，首先是一种贪心的方式。就是可以从上面留下来，然后不够就向左边要。类似于网络流？这道题我第一眼的做法其实是模拟最长不下降子序列之类的做法。考虑另一种做法：Dilworth 定理 题解 P3974 【[TJOI2015]组合数学】 ，参看这篇题解。有:

  1. 对于一个偏序集，其最少反链划分数等于其最大链的大小。
  2. 对于一个偏序集，其最少链划分数等于其最大反链的大小。
  3. 因此可以从右上向左下转移。

  此题还可以用线性规划对偶做。不是很会。

后记

还有一坨生成函数没搞。好多好多。今天就先结束了。明天还要测试，后天还要 THUPC。晚安(￣o￣) . z Z。