20251125

123456ph · 2025-11-25 20:53:21 · 个人记录

一个纯贪心题。难度在于直接贪心的错误性的发现或证明，以及超水的大样例。

简单来说。直接贪心是错的，需要打补丁。但是大样例能全过，所以就看你发没发现它是错的。

在看到大样例 T=1 的时候我愣了一下。但是我只想到 T=1 我多测可能出问题，没有想到 T=1 可以放过去错解。我就把大样例copy10遍再测了一次。过了。我就没有考虑正确性的问题了。

然后就WA了。

傻傻的去模样例。模了30min后找到规律。

【图片位招租】

很美妙的样例图，一眼就能看出很多性质。最后代码10min打完，感觉画这一张图30min不亏。

赛后得知可以直接dp。dp_i = \min(\max(dp_j+t_2j,ik)+t_2j+(i-j)t_1)。然后我发现我的柿子和这个一模一样。

但是呢。我这样省去了证明单调性的苦恼，也不会陷入【数据删除】的数据结构优化dp中。

感觉挺版。由于楼梯左部一定是一列，直接枚举。向右的最长长度是可 O(hw) 预处理的。然后就是单调栈例题了。

有两种解法：

最重要的就是 所有带环的问题全部换成序列上的问题。

（其实不止是环，树上的也可以拍成序列）。

我猜过不出现 010 或者 101 就是 YES 的结论（也就是一定可以调换顺序使得成立）。不会证。

如果我顺着刚刚那玩意往下的话，我会考虑最优的顺序，然后说不定就推出来了。

考场上想的是：第一问都不会，那还做啥。

这是错的。因为正解是构造最优，看能否满足条件。