·随着网上众多OIer的步子，大米饼便静静地做了以下题目。
·首先列出大米饼的码风(代码风格)：
①for循环被转化为Go循环和Ro循环分别表示升序和降序。②对于维护DP的单调队列，两个指针常用 Head和Tail两条。③对斜率优化一类题目的坐标点的宏定义X(i)Y(i)，便于理解同时使用double Rate函数计算两点直线斜率。
【1】玩具装箱（详细阐述） 【LINK】
步骤一：
列出DP方程式:设f【i】表示分组完前i件物品的最小花费,为方便计算，
设sum【i】表示是前i件物品的长度和。
f【i】=Min(f【j】+(sum【i】-sum【j】+i-j-L-1)2) 【0<=j
步骤二：
对于范围内的j,进行式子变形，获得直线解析式：（先让L++）
f【i】=f【j】+【(sum【i】+i)-(sum【j】+j)-L】2------->令s【k】=sum【k】+k
f【i】=f【j】+(s【i】-s【j】-L)2----------------->整体法展开
f【i】=f【j】+s【i】2+(s【j】+L)2-2s【i】(s【j】+L)---->移项
f【i】+2s【i】(s【j】+L)=f【j】+s【i】2+(s【j】+L)2---->转换为一般格式
b + kx = y
对于任意j可以表示为图像上一点J(s【j】+L,f【j】+s【i】2+(s【j】+L)2)，目的是求出f【i】,因为f【i】的值等于y=kx+b直线的截距。
步骤三：
问题转化为：对于一条斜率为k=2s【i】的直线（为什么将它作为斜率，请思考），使其至少过一点J(即上文那个任意J点,j
首先确定直线斜率的变化特点。由于k=s【i】2所以我们获得两个重要信息，即k>0并且k随i单调递增。我们将这个斜率画到图上，直线变化如下：
直线斜率的单调递增使得我们能够优化DP。怎么优化？优化的基础是，对于本题，在求最小值的背景下，我们维护一个下凸包，然后随着i的不断循环，凸包的尾巴(横坐标较小部分)会被逐渐削减，同时前端会不断变化。这个过程能够被单调队列完美胜任。去尾巴的原因在下图：
·由上文结论可以知道，只要我们的f【i】线过了一个J点，那么表示的是f【j】向 f【i】的状态转移。而我们的目的是使得f【i】线过了一个点并使其的截距最小(当然图中有不合理之处，本题中直线截距应当大于0)。图中可以看出，线段AB的斜率小于f【i】线的斜率，那么意味着f【i】线截距最小值时肯定不会过点A，因为可以通过平移到达更美妙的点B或点C等。所以我们就需要删掉队列中A点，因为后来的所有f【i】斜率必将大于AB,A点将会像凸包内的点一样对答案毫无价值。那么在前端加入点怎么解释呢？那也是同样的道理：
·在完成f【i】的状态转移后，i++。那么此时以前的f【i】也就成了f【j】中的一员，我们将它标记为点NEW。这个点是否有资格进入单调队列呢（即是否有资格作为候选的状态转移来源呢）就需要再次利用上文相同的思想。如图，如果 NEW点与A点组成的直线斜率小于线段AB,BC那么我们就要将BC两点从队首弹出，原因是既然有了NEW点的存在，那么以后的直线更愿意选择NEW点，因为这样会使截距更小。
·在代码实现“去除尾巴”和“清理头部”中，都是以判断斜率为标准。其实这类DP代码就是在原来基础上增加了单调队列的两排操作和一个求斜率的函数调用。
·代码之前的一个提醒：上文中的关于j的式子里出现了s【i】2,但不要错误理解为双变量，因为在对于同一个f【i】计算时，求斜率坐标相减就已经直接抵消掉了这个关于i的部分。
1 #include
2 #define ll long long
3 #define Empty (head>=tail)
4 #define go(i,a,b) for(int i=a;i<=b;i++)
5 const int N=50100;ll s【N】,Q【N】,f【N】,n,x,head,L,tail,j;
6 inline double X(ll i){return s【i】;}
7 inline double Y(ll i){return f【i】+(s【i】+L-1)(s【i】+L-1);}
8 inline double Rate(ll i,ll k){return (Y(k)-Y(i))/(X(k)-X(i));}
9 int main()
10 {
11 scanf("%lld%lld",&n,&L);s【0】=0;L++;head=1;tail=1;Q【1】=0;
12 go(i,1,n){scanf("%lld",&s【i】);s【i】+=s【i-1】;}go(i,1,n)s【i】+=i;
13 go(i,1,n)
14 {
15 while(!Empty&&Rate(Q【head】,Q【head+1】)[span style="color: rgba(128, 0, 128, 1)">2s【i】)head++;
16 j=Q【head】;f【i】=f【j】+(s【i】-s【j】-L)(s【i】-s【j】-L);
17 while (!Empty&&Rate(Q【tail-1】,Q【tail】)>Rate(Q【tail】,i))tail--;Q【++tail】=i;
18 }
19 printf("%lld\n",f【n】); return 0;
20 }//Paul_Guderian
【2】仓库建设【LINK】
步骤一：
列出DP方程式：设f【i】表示在i处建立一个美妙仓库，并且已经安置好i以前的所有货物的最小花费。为了便于计算，进行预处理：
对于k处货物向i地(i>k)运输，输入时有x【i】表示i到山顶的距离，p【i】表示仓库i货物数量，那么关于运输k处货物花费Wk=(x【i】-x【k】)p【k】。这样看难以进行前缀处理，所以拆开一看，哇：Wk=x【i】p【k】-x【k】p【k】
我们结合实际情况地定义这些数组来便于操作:令P【i】表示p【1~i】前缀和，令g【i】表示(-x【i】p【i】)的前缀和。我们可以顺利写出Dp方程式：
f【i】=min(f【j】+x【i】(P【i-1】-P【j】)+g【i-1】-g【j】+c【i】) 【0<=j
步骤二：
对于范围内的j,进行式子变形，获得直线解析式：
【一句提醒:由上文结论可知，如果变形出来的一部分式子仅与i相关，那么会在计算时被抵消，我们无须在意，但为了便于理解，使用蓝色标记这样的无意义的部分】
f【i】=f【j】+x【i】P【i-1】-x【i】P【j】+g【i-1】-g【j】+c【i】
f【i】=f【j】-x【i】P【j】-g【j】+x【i】P【i-1】+g【i-1】+c【i】
f【i】+x【i】P【j】=f【j】-g【j】+x【i】P【i-1】+g【i-1】+c【i】
b + kx = y
步骤三：
同上。使用单调队列维护，斜率K=x【i】保持单调递增，满足斜率优化的条件。本题需要额外注意的是f【i】的初始化，它的一个转移来源是把之前所有的货物都收进它的仓库，这个作为f【i】的初值就没问题啦。
代码GOGOGO：
1 #include
2 #include
3 #define ll long long
4 #define X(i) (1.0p【i】)
5 #define Empty (head>=tail)
6 #define Y(i) (1.0f【i】-g【i】)
7 #define go(i,a,b) for(int i=a;i<=b;i++)
8 const int N=1000006;
9 int n,tail=0,head=1,Q【N】;ll p【N】,c【N】,f【N】,x【N】,g【N】;
10 double Rate(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));}
11 int main()
12 {
13 scanf("%d",&n);
14 //代码效果参考：http://www.jhylw.com.cn/194134465.html
go(i,1,n)scanf("%d%d%d",x+i,p+i,c+i);15 go(i,1,n)g【i】=g【i-1】-p【i】x【i】,p【i】+=p【i-1】;
16 go(i,1,n)
17 {
18 f【i】=x【i】(p【i-1】)+g【i-1】+c【i】;
19 while(!Empty&&Rate(Q【head+1】,Q【head】)
20 int j=Q【head】;f【i】=std::min(f【i】,f【j】+x【i】(p【i-1】-p【j】)+g【i-1】-g【j】+c【i】);
21 while(!Empty&&Rate(Q【tail】,Q【tail-1】)>Rate(i,Q【tail】))tail--;
22 Q【++tail】=i;
23 }
24 printf("%lld\n",f【n】);return 0;
25 }//Paul_Guderian
【3】土地购买【LINK】
步骤一:
列出DP方程式：f【i】=? 咋整啊,这不是序列，方块可以任意选，而且不是连续的！卡机……
步骤O：
对于这道题，我们想要取得尽量少的总花费，有一个清晰的意识是我们要尽可能利用包含关系。如果一个矩形的长宽比一个矩形都小，那么我们就可以直接忽略！我们的目的求最小的花费，也就是最小的长乘宽的和，可以理解为几个矩形的面积和，如图:
在去掉被其他矩形包含的无用矩形的情况下，购买这两个矩形“套餐”的价格为：a x b。所以我们发现，蓝色的部分（即相较于原来矩形多出的部分）越小，我们的总共花费就越接近于矩形的本来面积（即图中的黑色和黄色矩形所占据的面积），这意味着我们只要使得矩形的长宽差异越接近，那么多出的蓝色部分花费就越少，由于矩形总面积不变，这样就使得总花费越小。怎样才能使得长宽接近？
SORT函数解决问题。我们将矩形长作为第一关键字，宽作为第二关键字，全都以从小到大加以排序。这样就使得长宽尽量接近。
这样做怎样去除包含矩形呢？我们发现对于排序后的矩形i，那么它的长必定大于等于i-1,宽的大小关系不定。如果我们发现i-1的宽也小于矩形i了那么说明这是包含关系——我们就像这样不断向前查找是否具有包含关系，直到i-k宽大于i为止。这样处理后的结果是：序列中的矩形的宽呈现递减关系（否则还会有包含关系），那么这样更加便于我们找到一段区间的宽的最值，DP方程式变得简单。
步骤一:
列出DP方程式：在排序后，设f【i】表示处理完前i个矩形的最小花费，且有i处作为一组的结尾。我们使用a【i】,b【i】分别表示矩形i的长和宽，根据宽的递减关系，以及a【i】单调递增，方程式如下,表示j是前一组的结尾，j+1到i是新的一个套餐：
f【i】=min(f【j】+a【i】b【j+1】) 【0<=j
步骤二：
对于范围内的j,进行式子变形，获得直线解析式：
f【i】=f【j】+a【i】b【j+1】
f【i】-a【i】b【j+1】=f【j】
b + kx =y 求直线的截距最小值。
步骤三：
代码直接就来了：
1 #include
2 #include
3 #define ll long long
4 #define Y(i) 1.0f【i】
5 #define X(i) 1.0S【i+1】.b
6 #define go(i,a,b) for(int i=a;i<=b;i++)
7 const int N=50003;
8 struct P{ll a,b;}S【N】;
9 ll f【N】;int n,q【N】,t,head=1,tail=1;
10 bool cmp(P A,P B){return A.a==B.a?A.bB.a;}
11 double Rate(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));}
12 int main(){
13 scanf("%d",&n);
14 go(i,1,n)scanf("%lld%lld",&S【i】.a,&S【i】.b);std::sort(S+1,S+n+1,cmp);
15 go(i,1,n){while(t&&S【i】.b>=S【t】.b)t--;S【++t】=S【i】;}n=t;
16 go(i,1,n)
17 {
18 while(head=-S【i】.a)head++;
19 int j=q【head】;f【i】=f【j】+S【i】.aS【j+1】.b;
20 while(head
21 }
22 printf("%lld",f【n】);return 0;
23 }//Paul_Guderian
【4】特别行动队【LINK】
步骤一:
列出DP方程式：设f【i】表示处理完前i个士兵的最高战斗力总和，并且在i处分出一组（i作为这一组的结尾）。sum【i】表示1~i的初始战斗力和(前缀)。
f【i】=max(f【j】+a(sum【i】-sum【j】)2+b(sum【i】-sum【j】)+c)
【0<=j
步骤二：
对于范围内的j,进行式子变形，获得直线解析式：
f【i】=f【j】+a(sum【i】-sum【j】)2+bsum【i】-bsu
