T1T2送的。
T3貌似有神仙优化方法，但是题解给的是容斥。（既然不好直接求满足条件的方案，就减去不满足条件的方案）。
T4的贪心就是：如果当前能走，就直接走，不然就向上或者向下走到第一个能走的地方。
证明：
假设之前贪心的方法能够取到一个最优解。
任意的走法为红色，贪心为蓝色。
然后你就发现可以通过平行四边形对边相等的性质，贪心走法在水平方向上的位移一样，竖直方向上的位移一定不劣。
不能走的情况，就一定是至少走到第一个能走的地方，然后一样贪心就行了。（走到第一个能走的地方这一步是唯一确定的，不管贪心与否都只能这么走）。