主要思路
我操这个题是真的有意思（做完后索然无味）。
肯定这个题状压 DP 没跑的，所以可以先设 \(f[S]\) 为集合 \(S\) 双连通的最小代价。直接做有点困难，我们需要思考一个归纳的方式来构造一个双连通图。
Continue reading →我操这个题是真的有意思（做完后索然无味）。
肯定这个题状压 DP 没跑的，所以可以先设 \(f[S]\) 为集合 \(S\) 双连通的最小代价。直接做有点困难，我们需要思考一个归纳的方式来构造一个双连通图。
Continue reading →狗屎状压题。
看到度数不超过 \(10\) 就知道需要状压儿子的信息。考虑处理一个 neck 数组来表示子树内节点到当前子树根下面的节点编号，然后我们每一次往上跳的时候我们都可以对这个数组进行调整，然后 DP 的时候就会比较愉快了。
处理 \(m\) 个请求的时候，我们把对应的 neck 提取出来，然后做标记，按标号小的进行 DP。
Continue reading →考虑超级暴力，设计状态\(dp[k][i][j]\)为走了\(k\)步处于\((i, j)\)的答案：
\[ dp[k][i][j] = mp[i][j] + \max \begin{cases} dp[k – 1][i – 1][j] \\ dp[k – 1][i + 1][j] \\ dp[k – 1][i][j + 1] \\ dp[k – 1][i][j – 1] \end{cases} \]