526互联

DP练!习!

发布时间 2023-11-07 16:06:27作者: _MikuFan

DP练!习!

都是水题啊 Made By M1kuFan

1 洛谷 P2513

求长度为 \(n\) ，逆序对个数为 \(K\) 的排列有多少个，答案对 \(1e9 + 7\) 取模

其中：\(1 \le n,K\le100\)

仅考虑从大到小向序列中插入每个数的位置，当前插入到了第 \(i\) 个。最少的时候对答案贡献为0，即插入到已有序列的最右边；最多的时候对答案的贡献为 \(i - 1\) ，即插入到了最右边。因此，排列中从小到大的第一个数对答案的贡献为 \([0,n - 1]\)，第 \(i\) 个数对答案的贡献为 \([0,n - i]\) 。

所以原问题转化为：构造一个长度为 \(n\) 的序列，令序列中第 \(i\) 个数为 \(x_i\) 求满足\(\forall i \in[1,n]\) , \(0 \le x_i\le n - i\) 且\(\sum x_i=K\)的方案数

不难写出从大到小枚举的转移方程：
\(f_{i,j}\) 表示长度为 \(i\) 的序列和为 \(K\) 的方案数 (\(1\le i\le n,1\le j\le K\))

枚举 \(k\) 表示第 \(i\) 个数选了什么，则：

\[f_{i,j} = \sum_{k = 0}^{min(i - 1,j)} f_{i,j-k} \]

边界：\(f_{0,0} = 1\)

前缀和优化或者吸一口氧+循环展开即可优秀地通过此题

2 简单题

给出一个 \(2 \times n\) 的网格，你现在需要用 \(n\) 个 \(2 \times 1\)的多米诺骨牌覆盖满整个网格（可以横着或者竖着放），求方案书

考虑现在进行到了第 \(i\) 列，\(ans_i\) 表示第 \(i\) 列之前（包含第 \(i\) 列）全部放满的方案数，有以下两种情况：

  1. 竖着放：则 \(ans_i = ans_{i - 1}\)
  2. 横着放：若横着放，则两行都应该是横着的，则 \(ans_i = ans_{i - 2}\)

所以：\(ans_i = ans_{i-1} + ans_{i-2}\)

边界：\(ans_1 = 1\)，\(ans_2 = 2\)

3.1 简单题2 ABC312D

给定一个为 \(N\) 的仅包含左括号、右括号、问号的序列，问号可以变成右括号或左括号，求最终的到合法括号序列的方案数量，答案对998244353取模。

\(N \le 3000\)

把左括号当成 \(1\) ，右括号当成 \(-1\) 。

令 \(f_{i,j}\) 表示枚举到第 \(i\) 个数，所有数的和 \(j\) 的方案数

转移有以下下情况：

  1. 当前是左括号，则：\(f_{i,j} = f_{i-1,j - 1}\)
  2. 当前是右括号，则：\(f_{i,j} = f_{i - 1,j + 1}\)
  3. 当前是问号，则：\(f_{i,j} = f_{i - 1,j - 1} + f_{i - 1,j + 1}\)

注意 \(j - 1\) 不要越界

边界: \(f_{0，0} = 1\)

3.2 学霸题（简单题2加强版）CF314E

给定一个长度为 \(N\) 的仅包含左括号和问号的序列，求最终得到合法括号序列的方案数量，答案对4294967296取模（注意给定括号序列不包含右括号）

\(N \le 100000\)，注意时限给到了4s

上面 \(N^2\) 的枚举显然不足以通过此题，所以我们要优!化!

注意到当右括号大于当前长度的一半的话，就会寄，一定不合法

所以我们可以把状态中的和为 \(j\) 改成右括号的个数为 \(j\) 。这样就减少了一半的枚举量

当前元素为左括号时 \(f_{i,j} = f_{i-1,j}\)

注意到 \(f_{i,j}\) 仅由上一层转移，所以我们可以滚！掉第一维

这样我们就可以仅在当前元素为问号时转移

另外模数是\(4294967296 = 2^{32}\) 要开unsigned int 自然溢出。

然后我们就可以优雅地通过此题

4 BZOJ2466

线性DP做腻了，来道树形DP!

给定一棵树，每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了，那么该节点的灯会从熄灭变为点亮（当按之前是熄灭的），或者从点亮到熄灭（当按之前是点亮的）。并且该节点的直接邻居也发生同样的变化。

开始的时候，所有的指示灯都是熄灭的。请编程计算最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。

\(1\le n \le 100\)

树形DP经典思路：根据儿!子!来确定父!亲！, 除非他没！有！儿！子！

不难想到以下思路：

我们不仅需要考虑一个点是开着还是关着，还需要关心一个点是否操作过，因为儿子的操作会影响到父亲，不难设计出如下状态，

\(f_{u,0/1,0/1}\) 代表保证 \(u\) 的子树中的点全都是开着的情况下：使 \(u\) 是关着/开着并且 \(u\) 操作过/未操作过的最小操作数

转移方程分情况讨论即可，非常简单：

\[\begin{cases} f_{u,0,0} = min(f_{u,0,0} + f_{v,1,0}, f_{u,1,0} + f_{v,1,1} )\\ f_{u,0,1} = min(f_{u,0,1} + f_{v,0,0}, f_{u,1,1} + f_{v,0,1}) \\ f_{u,1,0} = min(f_{u,1,0} + f_{v,1,0}, f_{u,0,0} + f_{v,1,1}) \\ f_{u,1,1} = min(f_{u,1,1} + f_{v,0,0}, f_{u,0,1} + f_{v,0,1}) \end{cases} \]

注意树形DP计算时要开中间变量避免错误

边界：

\(f_{u,0,0} = 0\)

\(f_{u,1,1} = 1\)

\(f_{u,1,0} = f_{u,0,1} = INF\) （不合法）

答案：

\(min(f_{root,1,0},f_{root,1,1})\)