这道题目肯定是费用提前计算
当然我们可以换一种理解方法来更严谨地理解费用提前计算
我们一开始就把所有的\(y\)求和,然后认为我们在行动过程中,有些彩蛋的价值会减损,显然我们就是要让这个减损值最小
然后我们发现由于我们不会走回头路(也就是在第一次经过某个彩蛋的时候一定会立马收集而不是等着),所以我们收集完一个区间的彩蛋后一定是位于左端点或者右端点,于是可设\(f[l][r][0/1]\)表示收集完这个区间的彩蛋并且位于左/右端点的所有彩蛋已经损耗的最小值,状态方程就不写了
类似题目:关路灯
标签:Sue,收集,小球,减损,彩蛋,端点,我们 From: https://www.cnblogs.com/dingxingdi/p/17988994