这场和 Youtube 主播 SecondThread 一个房间，（并且差点碾压了他！）
LGM 不过如此

这场掉分的应该都是猜结论失败然后被 D 题拉扯了太多的时间的缘故。。。

传送门

https://codeforces.com/contest/1616
https://t.me/algorithm_daily_of_minako/3222
https://www.facebook.com/dreamoon4/posts/6748183141918539

Problem D. The Winter Hike

给一个 2n x 2n 的矩阵，开始左上角 nxn 的子矩阵有棋子，你需要把这些棋子移动到右下角 nxn 的格子里，支持的操作是 shift 一行 or 一列，
矩阵中有一些障碍，对于每个障碍，你可以花费一个代价删除它，操作没有代价可以任意进行，只要不遇到障碍，问最少花费多少代价满足要求。

结论题，取这 8 个数 + 右下角矩阵的值。
00aa
00aa
aa00
aa00

Why？首先直接缩点 Dijkstra 是不够充分的的，反例是下面这种。

000—
00000-
000-0-
—000
—000
—000

虽然我们成功的将左上角的材料运输到右下角，但是没有足够的空间去华容道。
有简单的方法判断是否有足够的空间调整，就是只对目标区域的四个角进行缩点。

而这于我们开始所说的结论是等价的。

Problem E. New School

等价于动态维护括号序列的合法性。
直接离散化 + 线段树即可。

比赛时犹豫了好久最后决定写 SBT（唯一优势大概是不用离散化）。。。不过没能写完。。= =

• 线段树
• SBT

Problem F. Strange Instructions

给定一个 01 字符串，你可以对子串进行替换操作，使字符串变短同时产生一定得分：

1 – ’00’ -> ‘0’, +=a
2 – ’11’ -> ‘1’, +=b
3 – ‘0’ -> ”, -=c

并且还要求，一些操作之间不能相邻，问最大得分。

dp？

Problem G. Weighted Increasing Subsequences

给定一个数列 A，问所有递增子序列的权重只和。
数列 A 的递增子序列 a 的权重定义为，
a 中有多少项 > Sa，Sa 等于 A 中不包含子序列元素的后缀中的最大值。
（当后缀不存在时 Sa 为无穷大）

dp。