BZOJ3590:[SNOI2013]Quare – 题解

主要思路

我操这个题是真的有意思(做完后索然无味)。

肯定这个题状压 DP 没跑的,所以可以先设 \(f[S]\) 为集合 \(S\) 双连通的最小代价。直接做有点困难,我们需要思考一个归纳的方式来构造一个双连通图。

继续阅读BZOJ3590:[SNOI2013]Quare – 题解

「QuestOJ」盛大的庆典 – 题解

主要思路

狗屎状压题。

看到度数不超过 \(10\) 就知道需要状压儿子的信息。考虑处理一个 neck 数组来表示子树内节点到当前子树根下面的节点编号,然后我们每一次往上跳的时候我们都可以对这个数组进行调整,然后 DP 的时候就会比较愉快了。

处理 \(m\) 个请求的时候,我们把对应的 neck 提取出来,然后做标记,按标号小的进行 DP。

继续阅读「QuestOJ」盛大的庆典 – 题解

[Fortuna OJ]Aug 21 – Group A 解题报告

B – Maja

考虑超级暴力,设计状态\(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} \]

继续阅读[Fortuna OJ]Aug 21 – Group A 解题报告