12.09 考试总结
本次考试发挥一般，由于细节考虑不清楚、实现方法不正确挂了很多分，本来估分 \(100 + 30 + 30 + 0 = 160\) 分，结果只得了 \(60 + 60 + 25 + 0 = 145\) 分。
A
本题可以通过找规律来快速求解。但是我不擅长找规律，而且感觉这个题 DP 可做，遂写了个 DP。
设 \(f_{i,j}\) 表示首位为 \(j\) 且用了 \(i\) 根火柴棍的最小数。但是这样是不够的，因为 首位最小不一定整体最小，所以还需要对于每个状态记录一下对应最小值的位数。
枚举 \(i,j\)，可推出上一次用的火柴棍数量 \(i-cost_j\)，其中 \(cost_j\) 表示数字 \(j\) 耗费的火柴棍个数。
然后枚举上一次首位，只要可能就将其记录下来。然后对所有可能的转移进行排序。根据贪心原则，先按位数从小到大排序，位数相同再按首位数字从小到大排序，这样可以保证得到的数字最小。
对于询问，枚举首位数字的所有可能情况，再取其中最小值即可。
但是由于排序时 数组没判空，导致某些不合法情况可能进入考虑范围内，挂了 40 分。
B
由于输出具体方案，又由于数据非常小，所以考虑直接暴搜。理论上时间复杂度是 \(O(4^{n \times m})\) 次方，但是由于 每次搜索四个方向上分别只会跳到离自己最*的*台，而且不能 \(180\) 度转弯，所以复杂度远没有那么恐怖，暴搜即可通过。
但是考试时忘记了一件事：我写的 BFS，但是 BFS 是逐层扩散的，如果可行解在搜索树上深度较深就会 TLE。而 DFS 有更大概率快速找到可行解。就因为这个，挂了 \(40\) 分。
由此得到了一个经验：找解的存在性/一组可行解时，用 DFS 普遍情况下会更好；找最短路/最优解时，用 BFS 普遍情况下会更好。
C
考试的时候以为这道题是一道神仙数据结构题，就只打了个暴力。结果暴力打得不好，暴力分没拿满。
先考虑 \(x=0\) 的情况如何快速求解。
还是考虑搜索。不过对于每一个问号，我们按照 P，O，N，I 的顺序尝试填入。这样可以保证得到的第 \(k\) 组可行解就是字典序第 \(k\) 大的解。由于不用考虑加权，遂时间复杂度为 \(O(n+k)\)。
但是由于最终要考虑权值，所以可能会搜到非常多无效的状态，导致时间复杂度爆炸。这是如果我们考虑可行性剪枝：__如果当前权值加上后半未枚举部分的最大可能权值都达不到 \(x\)，那就直接将这个枝叶减掉。__这样可以减掉非常多的无用状态，而且后缀的最大可能权值也可以通过简单的 DP 预处理，可以 \(0 ms\) 通过。
这个题说明：DP 不仅可以是正解，还可以优化一些看似不可行的做法。
D
考试时一眼区间 DP，但是看起来状态就很难设，就直接放弃了。
根据区间 DP 的套路，状态的前两维肯定是记录区间。但是由于要将若干段区间删去，而转移方程中涉及区间最大值与区间最小值，所以光有两维状态不足以记录剩下的数的信息。
既然难以得到区间最大值与最小值，就将其设到状态里。而且由于 \(n \leq 50\)，所以值的种类不会很多，验证了此做法的可行性。
设 \(f_{l,r,ma,mi}\) 表示区间 \([l,r]\) 中删去了一些数，剩下的数里最大值是 \(ma\)，最小值是 \(mi\) 的最小代价。
有两种转移：
\(1.\) 直接往区间里加入端点
可以直接将右端点加入区间，影响区间剩下数的最大值和最小值。但由于 \(\max\) 和 \(\min\) 运算不可逆，所以通过枚举之前的最大值和最小值来转移较为困难，所以可以用刷表法，直接求得新区间的最大、最小值。方程为：
\(2.\) 删除一段区间
这肯定要枚举断点。对于断点，再考虑三种情况：
\((1)\) 最大值、最小值都在断点左侧
此时断点右侧区间要全部删完。所以我们还需要记录一个 \(g_{l,r}\) 表示将区间 \([l,r]\) 中的数删完的最小代价。
设 \(k\) 为断点，方程即为：
\((2)\) 最大值、最小值都在断点右侧
类比 \((1)\)，可得：
\((3)\) 最大值、最小值在断点两边
此时可以移动断点，进行等效转移。而且，在同侧的情况一定优于在异侧的情况，遂不需考虑。
而 \(g\) 数组非常好转移，就是将区间内剩下的数全部删完即可。方程为：
可以发现， \(f\) 和 \(g\) 是相辅相成的。
综上，我们得到了完整的做法，时间复杂度为 \(O(n^5)\)。但是在初始化时需要注意：一个区间内剩下数的最大值和最小值恰与不删时的值相同的代价为 \(0\)。
总结一下：DP 中遇到不好通过计算等简单手段得出的信息，可以尝试将其加入状态中，可能会更方便。