ZLOJ 练习？总结

爆炸练习

总结：不要倒序开题。

A,B 都还是比较简单的吧，A 思路偏了，贪心有点问题，B 比赛的时候根本没有细想，其实状态和转移都蛮简单的。

$C$ 题的题意转化还是很有意思的，原先一直想着在一维数轴上做，但是很显然这样是无法自然地得出贪心选择的思路的。

关键的题意转化，在于列出式子 $t_j-t_i\geq |x_j-x_i|$。以 $x$ 为横坐标，$t$ 为纵坐标，建立二维坐标系，那么观察图像可以发现包含区间是两条 $45$° 线构成的半平面交，这时为了方便不妨将坐标轴旋转 $45$°，同时又只关注相对大小，则不妨令新坐标变为 $t+x,t-x$。以此为突破口设计贪心思路。

总结：遇到有两种限制的类似贪心题，可以考虑列出式子，并尝试在二维坐标系中表示，进一步寻找贪心思路。

写 $D$ 的感觉真是奇怪。。。。

一开始题目看错，主观以为 $U,D$ 只要是一个子序列就行了，一直不知道该怎么写才好，看题解也看得懵懵的。

后来总算发现了正确的题意，没想到一想就是枚举字符串的思路，根本没想到在原序列上搞，这个思路怎么优化好像都有一个 $n^2$，看了看第三篇题解，大致理解了意思就用那种方法打下来了，心想考试怎么能想到。

过了这题之后，看了看同机房神犇们的代码，大悟，原来用刷表的形式更新 DP 数组就可以了，至于如何判断是上还是下，只要结合数值判断就行了。

到现在还不是很清楚为什么自己的思路绕了这么一个大圈还是没有想到这最简单自然的方法。