上午 NOIP模拟赛
A
猜了结论。
一个一个数做。当前这个数插进去的时候，设前驱为pre[i]，后继为nxt[i]。
设 \(x = max(a[pre[i]], a[nxt[i]])，y = min(a[pre[i]], a[nxt[i]])\)。
则：
当 \(a[i] > x\) 时，\(ans += a[i] - x\);
当 \(a[i] < y\) 时，\(ans += y - a[i]\);
否则 \(ans\) 不变。
不变还是好理解的，因为原来的方案里面 \(x\) 加到 \(y\) 的过程把 \(a[i]\) 包含了。
其他时候感觉可以理解成把 \(a[i]\) 和 \(x\) 或者 \(y\) 先并成一个数，再按照原来的方案操作。
考试的时候一下就想到了这个结论，但是数组开小了，还是写太快了/qd。100 -> 40，输。
B
考试的时候写了个假的 dp，输。
考试后学习了 @QAQfj5 的超绝单调队列。
考虑维护一个冰箱。
把所有能选的棒冰都尽量塞进冰箱里。
对于当前的 \(i\)，如果吃到的棒冰是在位置 \(j\) 买的。那么每根棒冰在 \(j\) 买完再保存到 \(i\) 耗费的代价就是 \(p[j] + (i - j) * m\)。
显然要选这个代价最小的位置来买棒冰。把 \(i * m\) 提出来，剩下的就是 \(p[j] - j * m\)。把这个丢进单调队列里面维护，就可以得到代价最小的 \(j\)。
如果冰箱容量不限。显然每次取队头就可以。
考虑怎么维护冰箱的容量。
考虑对于每一天的棒冰，在冰箱里存它能买的最大个数。
具体实现就是在单调队列里塞二元组。
\({x, y}\) 表示在位置 \(x\) 买的棒冰，最多还存着 \(y\) 根。
每次对于位置 \(i\)，先从队头开始吃存着的棒冰，如果存货不够再新买来吃。
最后用第 \(i\) 个位置买的棒冰填满冰箱。此时填的个数就是维护出了位置 \(i\) 最多存几根棒冰在冰箱里。
按照思路就能把代码实现。非常好贪心。
反省一下，考试的时候首先不能打错暴力，否则优化也是前功尽弃。
其次，也不能被自己想的 dp 束缚，积极考虑人类智慧做法。