这篇题解被手贱的我不小心删掉了
，没办法，再打一次吧。
T1 积木大赛
这题的题意非常清楚，暴力$\mathcal{O}\left( nh\right)$的做法显然是不对的，可以用下面这个线性时间复杂度的做法：
每读入一列的高度，如果它比上一列高，就把答案递增两列高度之差，因为高出来的这些行必须用一个新的操作来填上，否则不用修改答案，因为这一列的每一行都可以由上一列延伸过来。
代码在此。
T2 花匠
这题思路和求LIS的思路非常相似。
维护两个序列，分别满足条件A和条件B，两者操作基本一致，我以条件A为例。
首先把第一株花的高度加入序列，然后枚举每一株花，这里要按序列长度的奇偶性讨论，操作也基本一致，我以奇数为例。
若高度小于序列的末尾元素，就把它加入到序列末尾，这样一定满足条件；否则就用该高度替换末尾元素，因为下一个元素要小于末尾元素，在不影响其他的前提下，末尾元素更大显然更优。
最后取较长的那个序列就行了。
代码在此。
T3 华容道
这题虽然实现起来代码较长，但思路还是很清晰的。
暴力BFS的时间复杂度高达$\mathcal{O}\left( n^4\right)$，再加上有多个询问，会TLE。考虑用最短路做。
求解每一个询问可以分为两步，先把空白块移动到目标棋子旁边，然后利用空白块把目标棋子移动到目标位置。
第一步BFS一遍就行了，第二步就有些麻烦。
设$f_{i,j,k}$为目标棋子在点$\left( i,j\right)$，空白块在目标棋子的k方向上这个状态。可以用各个$f$之间的转移构造出一张图，回答询问时在图上跑SPFA就行了。
代码在此。
评论 (0)
