OJ 传送门
原题: QOJ 5500
题意
有 \(n\) 个屋子排成一列，每个屋子里一个人，每个屋子可以开酒吧。
每个人会去自己左右两侧最近的（分别）酒吧消费。
一个方案的价值为 \(\sum _ {酒吧} 来这个酒吧的人数 \times p_i\)，其中 \(p_i\) 给定，求最大价值。
思路
显然是一个 dp？
转移顺序应该是什么 \(dp_j \rightarrow dp_i\)。
\(dp_i\) 表示只考虑前 \(i\) 个人和酒吧，强制 \(i\) 位置开酒吧，此时的最大价值。
接下来是优化：
你发现这既不能斜率优化（两个既包含 \(i\) 又包含 \(j\)），也不决策单调（打表发现）。
然后平凡的 dp 就倒闭了，接下来的优化思路其实是脱离 dp 本身的，只有这个 dp 式有用。
优化思路 1
你是人类而非奶龙。
你注意到如果把 \((i, p_i)\) 画在坐标轴上，那么 \((i - j) \times (p_i + p_j)\) 就是一个梯形面积（不管系数）。
那么就转换成找出若干个点，相邻的梯形面积和最大，如上图感性理解，显然维护凸包。
优化思路 2
我是奶龙而非人类。
我会调整发推导最优解的性质。
假设 \(x \lt y \lt z\)，且取 \(y\) 优于不取，则展开式子：
然后我们需要发现这里有相似的结构：\(ip_j - jp_i\)，记为 \(f(i,j)\)。
其实 \(f(i,j)\) 就是向量 \(\vec(a) = (i, p_i) , \vec(b) = (j, p_j)\) 的叉积，转换成几何意义：
就是图 1 的黄色和绿色三角形面积和要大于图 2 的蓝色三角形面积，推导出要满足 \((y, p_y)\) 在 \((x, p_x)\) 和 \((z, p_z)\) 连成的直线上方。
等价于维护凸包。