-
给定一个序列，每次可以将两个相邻且相同的数合并成一个数，合并结果为原数加一。求最后能得到的最大数字。
-
\(n \le 248\)，\(1 \le a_i \le 40\)。
最暴力的，设状态 \(f_{l, r, k}\) 表示区间 \([l, r]\) 能否最终合并为数字 \(k\)。也就是说 \(f_{l, r, k}\) 是一个 bool 值。
由于 \(k\) 一定是由两个 \(k - 1\) 合并而来的，所以转移为 \(f_{l, r, k} = \operatorname{or}_{p=l}^{r-1} \{f_{l, p, k - 1} \operatorname{and} f_{p + 1, r, k - 1}\}\)。
这样是可以通过的。
可以发现，如果一个区间 \([l, r]\) 能合并成数 \(k\)，那么这个 \(k\) 是唯一的。也就是一个区间不可能合并成两个及以上的数。
所以这个三维状态显得很愚蠢。我们重新设 \(f_{l, r} = k\) 表示区间 \([l, r]\) 最终能合并出来的数 \(k\)。若不能合并为 \(-1\)。然后做类似转移即可。
-
题意同上。
-
\(n \le 262144\)，\(1 \le a_i \le 40\)。
仍然是区间 DP。但是显然状态不能设成 \(f_{l, r}\) 这样 \(\Theta(n^2)\) 的。
同时仍然可以发现，对于两个有着相同左端点和不同右端点的区间 \([l, r], [l, r']\)，那么一定有 \(f_{l, r} \ne f_{l, r'}\)。
我们重新设状态。考虑将其中一维放在状态之外。具体的，设状态 \(f_{l, k} = r\) 表示若左端点为 \(l\)，右端点 \(r\) 是多少时区间合并的结果为 \(k\)。根据上面所说，这个值是唯一的。
转移 \(f_{l, k}\) 时，我们需要找到两个相邻的区间 \([l, m], [m + 1, r]\)，而且这两个区间合并出来的数都需要是 \(k - 1\)。不难发现 \(m = f_{l, k - 1}, r = f_{m + 1, k - 1}\)。所以转移为 \(f_{l, k} = f_{f_{l, k - 1} + 1, k - 1}\)。
-
求在 \(n \times m\) 的棋盘上棋子，且不存在某一行或某一列有大于两个棋子的方案数。
-
\(n, m \le 100\)。
设状态 \(f_{i, a, b, c}\) 表示只考虑前 \(i\) 行，且共有 \(a\) 列上放 \(0\) 个棋子，\(b\) 列上放 \(1\) 个棋子，\(c\) 列上有 \(2\) 个棋子。可以发现如果已知 \(a, b\) 可以求出 \(c = m - a - b\)，所以状态改为三维 \(f_{i, a, b}\)。
接下来枚举第 \(i\) 行放 \(0 \sim 2\) 个棋子，然后将这些棋子分配到不同列然后分类讨论。
为了方便可以写成刷表。
-
给定一个序列，有如下操作：
- 选择两个相邻且相等的数字，将其合并为两个数的和。
- 选择三个相邻且左右两个相等的数字，将其合并为三个数的和。
求最后能得到的最大数字。
-
\(n \le 400\)。
不难发现如果一个区间能合并成一个数，那么这个数一定是这个区间的和。
所以可以设 bool 状态 \(f_{l, r}\) 表示区间 \([l, r]\) 能否合并成一个数。转移显然可以枚举断点。记 \(s(l, r) = \sum_{i=l}^r a_i\)：
- 第一种操作：\(f_{l, r} = \operatorname{or}_{k=l}^{r-1}\{[s(l, k) = s(k + 1, r)] \operatorname{and} f_{l, k} \operatorname{and} f_{k + 1, r}\}\)。
- 第二种操作：\(f_{l, r} = \operatorname{or}_{k = l}^{r - 1} \operatorname{or}_{p=k}^{r - 1} \{[s(l, k) = s(p + 1, r) ]\operatorname{and} f_{l, k} \operatorname{and} f_{k + 1, p} \operatorname{and} f_{p + 1, r}\}\)。
直接转移是 \(\Theta (n^4)\) 的，卡常可过。
我们注意到对于第二种操作的 \([s(l, k) = s(p + 1, r)]\) 判断，由于 \(a_i\) 均非负，所以在 \(l, r\) 一定时，随着 \(k\) 的增大，\(p\) 一定不减。
所以 two-pointer 即可。
-
给定一个由字母 \(\texttt{WING}\) 组成的字符串和若干个变化规则，表示可以将相邻两个字母合并成一个字母。求这个字符串可以合并为哪些独个字母。
-
\(n \le 200\)。
设 bool 状态 \(f_{l, r, k}(k \in \{\texttt W, \texttt I, \texttt N, \texttt G\})\) 表示区间 \([l, r]\) 能否合并成 \(k\)。
转移枚举断点 \(k\) 然后判断是否存在一种规则将左右两段区间合并成 \(k\)。
- P4170 [CQOI2007] 涂色
- 有 \(n\) 个位置，最初均没有颜色。每次操作可以选择一个区间并覆盖同一种颜色。求最小操作次数使得与目标状态相同。
- \(n \le 50\)。
设状态 \(f_{l, r}\) 表示将区间 \([l, r]\) 染成目标颜色的最少操作次数。
观察发现，如果我们想将一个区间 \([l, r]\) 全部染成目标颜色，那么第一步就可以将整个区间涂上同一种颜色。然后再慢慢调整。
同时，对于区间的左/右断点，显然如果将其染色大于 \(1\) 次显然不优。但对于中间位置不受影响。
所以我们可以在第一步就将整个区间涂成左端点的颜色。
此时，若左右端点颜色相同，我们可以染色区间 \([l, r - 1]\) 或 \([l + 1, r]\)，然后在第一步染色时多染一格。
否则，枚举断点 \(k\)，左右分别染色。
标签：状态,le,合并,端点,区间,operatorname,DP From： https://www.cnblogs.com/2huk/p/18068631