比较神奇的dp题.其实也不能算dp辣ovo
有一个神奇的事情是,塔的高度与底层的宽度是负相关的.
所以就变成了问塔底最窄的时候塔有多高.
用f[i]来表示用从第i个砖块到第n个砖块搭起来的塔的最窄底层宽度.用s[i]来表示宽度的前缀和,然后得到一个式子:
f[i] = min(s[j-1]) - s[i - 1] (f[j] ≤ s[j - 1] - s[i - 1], j > i)
s是单调的.看上去很像是dp呢.
然后就变成了求s[j - 1] - f[j] ≥ s[i - 1]时的最大的s[j - 1].于是开单调队列搞吧ovo