Description 　　P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压 缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1…N的N件玩具，第i件玩具经过 压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容 器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形

传送门 HNOI2008 All Clear! 这个题貌似有三种做法。。 首先可以斜率优化dp 然后可以证（da）明（biao）发现决策单调性 之后根据这个结论有两个做法： 1.每次算出来一个dp[i]，就往后二分查找影响区间的变化点x，然后将[x,n]涂上i 然后按照这样递推算出来就好了，涂色用线段树， O(nlog2n) O(nlog^2n) 2.用单调队列和二分查找，具体可以

题目请点击这里 首先可以得到方程： f[i]=max{f[j]+(sum[i]-sum[j]+i-j-1-L)^2} 显而易见该方程具有单调性，因此可以使用决策单调性优化，维护一个下凸壳，每次将当前队首决策取出直至当前决策为最优，然后将当前点加入队尾，若有斜率小于当前点的则先取出后加入。 /*User:SmallLanguage:C++Problem No.:1010*/#