澡堂游记 DAY1-1
概要
5.1日上午内容主要为序列、区间dp
5.1日下午主要内容为背包
动归概论
动态规划本质上是记忆化搜索
即将搜索过程中的遇到的已搜索结果保存并转移
因省去递归结构减少常数时间复杂度
所以核心是如何标记并存储状态并从较小规模答案得到较大规模答案
例题
1.求长度为 n 的合法括号序列有多少个，对 10^9 + 7 取模
可以发现 这就是卡特兰数的定义：$ T_0,T_n=\sum^{n-1}{i=0}T_i*T{n-i-1}$
通项公式：$T_n=(^{2n}{n})-(^{2n}{n-1})=(^{2n}_{n})/(n-1)$
序列的任意前缀左括号个数大于等于右括号
考虑图形：
即得答案
2石子合并
跳过。。。
3LCS 计数
给定两个串求他们 LCS 的长度以及个数。
|s|, |t| ≤ 5000
参照一般的 LCS 方法，在 DP 的同时统计方案数即可
对于相同 使用加法原理与容斥原理 $f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]$
显而易见 鲜矣仁
4Flappy Bird
小鸟一开始位于 (0, 0) 处，它的目标是飞到横坐标为 X 的某个
位置上。
每一秒，你可以选择点击屏幕，那么小鸟会从 (x, y) 飞到
(x + 1, y + 1)，或者不点击，那么小鸟会飞到 (x + 1, y - 1) 。在
游戏中还有 n 个障碍物，用三元组 (xi, ai, bi) 描述，表示在直线
x = xi 上， y ∈ [ai, bi] 的部分都是障碍物，碰到或者擦边都算游戏
失败。请求出小鸟从 (0, 0) 飞到目的地最少需要点击多少次屏幕。
n ≤ 5 × 105。
首先，横纵坐标奇偶性不同的位置是小鸟无法到达的。
然后我们旋转坐标系，使得 (x, y) 变为 (x, x+2y)。
于是，点击屏幕的结果变成 (x + 1, y + 1)，不点击屏幕的结果变
成 (x + 1, y)，每个柱子依然是一段纵坐标上的区间，于是扫一遍
维护一个纵坐标可行区间即可。
时间复杂度 O(n)。
5涂色
跳过。。。
6Clear the String
与上题雷同
给你一个串 s，每次可以删去由同一个字符组成的一个子串。
求删去整个串的次数。
1 ≤ |s| ≤ 500。
flr 表示删去 [l, r] 的子串的最小代价。
考虑转移：
首先可以直接删去尾，即 flr = flr-1 + 1。然后考虑枚举中间哪个
字符和 r 位置的字符一起被删去，假设枚举的位置是 k，那么
flr = flk + fk+1r-1，因为 sk = sr，所以两个位置可以一起删去而
不需要耗费额外的代价。
7 中国象棋
在一个 N 行 M 列的棋盘上，让你放若干个炮（可以是 0 个），
使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。
在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅
当它们在同一行或同一列中，且它们之间恰好有一个棋子。
N, M ≤ 100。
我们把题目中的限制转化一下，就是每一行每一列放的炮的个数
不能超过 2。
我们按行来放置，设 fijkl 表示当前放到了第 i 行，其中有 j 列放
了 0 个炮，有 k 列放了 1 个炮， l 列放了两个包
8RGB Sequence
有 n 个格子，你要给他们染上红/绿/蓝中的一个颜色。
有 m 个限制，每个限制形如 (l, r, x)，表示 [l, r] 区间内出现的颜
色的数量恰好是 x。
求总的染色方案数。
n, m ≤ 300, x ∈ {1, 2, 3}。
出现的颜色个数容易考虑枚举区间右端点维护每个颜色最后出现
的位置来判断。
一个显然的想法是设 fijkl ] 表示当前考虑到了第 i 个格子，红绿
蓝三种颜色最后一次出现的位置分别是 j, k, l 的方案数。
由于 i = max(j, k, l)，只需要记录后几维状态即可。
对于限制而言，我们把限制挂在右侧，当 dp 到右侧点时向左考
虑每个颜色的最后出现位置即可。