AT_agc017_f [AGC017F] Zigzag 题解 / 轮廓线 DP 学习笔记
zrl123456
·
·
题解
:::::info[题目基本信息]
考察：动态规划 DP，轮廓线 DP，状压 DP（3417）。
题目简介：
给定一个每条边由 n 个点构成的正三角形，(i,j) 表示三角形中从上往下第 i 行，从左往右第 j 个点，现在有 m 条折线，每条折线从 (1,1) 出发，每次向左下或右下移动，问满足以下条件的折线序列个数（对 10^9+7 取模）：
-
- 给定 k 以及序列 \{a_k\},\{b_k\},\{c_k\}，对于第 a_i 条折线，在第 b_i 次移动时必须选择左下（c_i=0 时）或右下（c_i=1 时）方的点。
数据范围：
-
1\le n,m\le \color{red}{20}
-
0\le k\le (n-1)m
-
\forall i\in[1,k],1\le a_i\le m,1\le b_i<n,c_i\in\{0,1\}
-
\forall 1\le i<j\le k,(a_i,b_i)\ne(a_j,b_j)
时间限制：4s。
空间限制：256MB。
:::::
如果我们直接暴力状压 DP，设 f_{i,S} 为考虑到第 i 条折线，同时第 i 条折线的向右移动的时刻构成的集合为 S 时的方案数，那么时间复杂度高达 \Theta(4^nnm)，看上去没救了。
我们转化一下问题，转化为在一个 m\times (n-1) 的网格中填数，限定若干个位置必须填 0 或 1，同时 \forall 1\le i<j\le m,1\le k<n，第 i 行不满 k 个 1 或者第 j 行满 k 个 1 且第 i 行的第 k 个 1 的下标小于等于第 j 行，容易发现这两个问题等价。
在网格图上做状压 DP，我们很容易（也可能不太容易）想到轮廓线 DP，在转化后问题中我们可以设 f_{i,j,S,p} 为考虑到第 i 行第 j 个数下轮廓中填 1 的列编号构成的集合为 S，同时第 i-1 行前 j 个数中有 p 个 1 的方案数，容易发现转移为 \Theta(1)，这样总复杂度就为 \Theta(2^nn^2m) 的，仍然过不去。
这时我们考虑删去 p 这一维，并把他记录到 S 这一维中，显然在上一行填 0 这一行填 1 时上一行右边离它最近的 1 处可以填 0，若填 0 就是填补了这两行间的差距，填 1 就仍然是这一种情况，下一个 1 处可以填 0，容易发现正确性成立。
这时状态减少到了 \Theta(2^nnm) 级别，转移仍为 \Theta(1)，至于空间问题滚动数组压掉 i,j 两维即可。
时间复杂度为 \Theta(2^nnm+k)，空间复杂度为 \Theta(2^n+nm)。
code