CF771E Bear and Rectangle Strips
Alex_Wei
·
·
题解
CF771E Bear and Rectangle Strips
这题好难啊。
首先，容易借助 map 或其它 STL 求出 na_i, nb_i, nc_i 分别表示从第 i + 1 列开始，合法子矩形的右边界的最小值，且该合法子矩形占用第一行 / 第二行 / 第一、二行。
显然有 naive 的 DP：设 f_{i, j} 表示只考虑第一行前 i 列和第二行前 j 列的答案。转移即不选取子矩形转移到 f_{i + 1, j}, f_{i, j + 1}，选子矩形转移到 f_{na_i, j}, f_{i, nb_j}, f_{nc_{\max(i, j)}, nc_{\max(i, j)}}。这个 DP 显然也是过不去的。
尝试减小状态数到 \mathcal{O}(n)。自然的想法是设 f_i 表示原 f_{i, i}。
考虑任意选择子矩形的方案，我们总可以每次选择左端点最靠左的矩形，为每个方案钦定其中所有子矩形被考虑到的顺序。
考虑原 f_{i, j}(i\leq j)。若 f_{i, j} > f_{i, i} + 1，则 f_{i, j} 对应的方案中，一定存在一个子矩形占用了第二行的第 i + 1 列，且其右侧还有一个子矩形。否则与 f_{i, i} 的最大性矛盾。设倒数第二个子矩形覆盖第二行的第 [p, q] 列，接下来我们将说明 f_{i, j} 是不必要的：
- 如果第一行的第 [i + 1, q] 列没有被子矩形覆盖，则可以先转移到 f_{q, q}，再转移到 f_{q, j}。
- 如果第一行的第 [i + 1, q] 列被子矩形覆盖，则该子矩形的左端点小于第二行最后一个子矩形的左端点，它应该先被枚举到，故 f_{i, j} 不合法。
接下来，根据值域定义域互换的套路，只有使得 f_{i, j} = f_{i, i} + 1 的最小的 j 是重要的。同理，还需记录使得 f_{j, i} = f_{i, i} + 1 的最小的 j。分别记它们为 g_i 和 h_i。
首先要确定 f_i，才能求出 g_i, h_i。对每个 i 记录所有转移到 f_{i, j}(i\leq j) 的 j 以及对应值 v 形成的二元组 (j, v) 即可。
这样，总共只需考虑 \mathcal{O}(n) 种状态，而每种状态只有 \mathcal{O}(1) 个后继。因此，DP 部分的时间复杂度为 \mathcal{O}(n)。
总时间复杂度 \mathcal{O}(n\log n)。代码，注意 g, h 的定义是反的。
可以做到多次询问 f_{i, j}，有空再补。