P6275 [USACO20OPEN]Sprinklers 2: Return of the Alfalfa P 题解
一道很妙的 DP 题，一眼过去感觉这好像是个轮廓线 DP，然后这道题确实是轮廓线 DP 但不是 \(2^n\) 那种的。
本篇题解参照了其他题解的思路 （我从来没写过这种套路的题），在此表示感谢。
首先规定一下本文中的 \((i,j)\) 不是指第 \(i\) 行第 \(j\) 列，而是指网格线的第 \(i\) 行第 \(j\) 列这个点，如下图所示：
红色点就是 \((4,5)\)。
这道题的轮廓线就是从 \((0,0)\) 到 \((n,n)\) 的一条往右下线。
设 \(f_{i,j,0/1}\) 表示前面 \(i\) 行都全部覆盖，当前轮廓线终止在 \((i,j)\)，轮廓线的最后一根方向是往右还是往下时的方案数。
首先看几个结论：
- 轮廓线的拐点数就是必须要放的洒水器数。
比如说下图，有 5 个拐点，那么就要放 5 个洒水器。
- 假设上图必须要放 \(k\) 个洒水器，整张图能放洒水器的面积为 \(S\)，那么对于当前轮廓线的总方案数为 \(2^{S-k}\)。
这个结论还是很明显的吧，就是因为剩下的点可放可不放，而且每个点能放的洒水器数量只有一种。
好的又设 \(sum_{i}\) 表示这一行的能放洒水器的数量（空地数），可以开始推方程了。
对于 \(f_{i,j,0}\)：
我们发现其需要从 \(f_{i,j-1,0/1}\) 转移。
- 从 \(f_{i,j-1,0}\) 转移。
此时是这样的：
发现拐点数没变，覆盖总面积也没变，因此 \(f_{i,j-1,0}\) 的贡献是 \(f_{i,j-1,0}\)。
- 从 \(f_{i,j-1,1}\) 转移。
发现新增了一个红色的洒水器，总面积没变，对应的 \(2^{S-k}\) 变为 \(2^{S-k-1}\)，因此 \(f_{i,j-1,1}\) 的贡献是 \(\dfrac{f_{i,j-1,1}}{2}\)。
综上，\(f_{i,j,0}=f_{i,j-1,0}+\dfrac{f_{i,j-1,1}}{2}\)。
对于 \(f_{i,j,1}\)：
注意 \(f_{i,j,1}\) 需要从 \(f_{i-1,j,0/1}\) 转移过来，因此面积数和拐点数都有变动。
\(f_{i-1,j,0}\) 的贡献：面积数增加 \(sum_i\)，拐点数增加 1，方案数变化为 \(2^{S-k} \to 2^{S-k+sum_i-1}\)，因此贡献是 \(f_{i-1,j,0} \times 2^{sum_i-1}\)。
\(f_{i-1,j,1}\) 的贡献：面积数增加 \(sum_i\)，拐点数不变，方案数变化为 \(2^{S-k} \to 2^{S-k+sum_i}\)，因此贡献是 \(f_{i-1,j,1} \times 2^{sum_i}\)。
所以 \(f_{i,j,1}=f_{i-1,j,0} \times 2^{sum_i-1}+f_{i-1,j,1} \times 2^{sum_i}\)。
这一组转移可以参考下面两幅图：
注意 DP 的时候 \(i : \text\color{red}{0} \to n,j : \text\color{red}{0} \to n\)，整体代码还是很好写的。
Code：GitHub CodeBase-of-Plozia P6275 [USACO20OPEN]Sprinklers 2 Return of the Alfalfa P.cpp