关键词：
对于有i*j的项，考虑用斜率优化DP（任务安排）
http://poj.org/problem?id=1180 单调递增
1 memset(f,8,sizeof(f));f[0]=0; 2 FOR(i,1,n) 3 4 while(l<r && (f[q[l+1]]-f[q[l]])<=(sumc[q[l+1]]-sumc[q[l]])*(sumt[i]+s)) ++l; 5 f[i]=f[q[l]]-(sumt[i]+s)*sumc[q[l]]+sumt[i]*sumc[i]+s*sumc[n]; 6 while(l<r && (f[i]-f[q[r]])*(sumc[q[r]]-sumc[q[r-1]])<=(f[q[r]]-f[q[r-1]])*(sumc[i]-sumc[q[r]])) --r; 7 q[++r]=i; 8
https://www.lydsy.com/JudgeOnline/problem.php?id=2726 不单调，二分
1 FOR(i,1,n) 2 3 int L=l,R=r; 4 while(L<R) 5 6 int mid=(L+R)>>1; 7 if(f[q[mid+1]]-f[q[mid]]<=(s+sumt[i])*(sumc[q[mid+1]]-sumc[q[mid]])) L=mid+1; 8 else R=mid; 9 10 int p=q[L]; 11 f[i]=f[p]-(sumt[i]+s)*sumc[p]+sumt[i]*sumc[i]+s*sumc[n]; 12 while(l<r && (f[i]-f[q[r]])*(sumc[q[r]]-sumc[q[r-1]])<=(f[q[r]]-f[q[r-1]])*(sumc[i]-sumc[q[r]])) --r; 13 q[++r]=i; 14
单调队列和斜率优化是属于决策单调性的一种。而决策单调性是满足四边形不等式的前提下，满足i+1-n的转移点大于等于i的决策点。而基本实现方式是整体二分或者维护双端队列并且在双端队列上二分查找。
1.基于1D/1D的DP优化
一般来说，1D/1D的DP都能通过优化，在O(nlogn)O(nlogn)的时间复杂度之内转移完成。
例子：
1.f[i]=min/maxf[j]+s[j,i];f[i]=min/maxf[j]+s[j,i];(s[i,j]s[i,j]表示的是从j向i转移的时候，s[i,j]s[i,j]的每一项只与ii或jj相关，并且jj的选择区间是连续的)
单调队列！O(n)O(n)解决！
2.f[i]=min/maxf[j]+s[j,i]f[i]=min/maxf[j]+s[j,i];(s[i,j]s[i,j]表示的是从j向i转移的时候，s[i,j]s[i,j]的每一项只与ii或jj相关，jj的选择区间是满足一定性质的)
数据结构！O(nlogn)O(nlogn)解决！
3.f[i]=min/maxf[j]+s[j,i]f[i]=min/maxf[j]+s[j,i];(s[i,j]s[i,j]表示的是从j向i转移的时候，s[i,j]s[i,j]的每一项最多与calc(i)×calc(j)calc(i)×calc(j)相关，calc(i),calc(j)calc(i),calc(j)均有单调性，j的选择区间是连续的)
斜率优化！O(n)O(n)解决！
4.f[i]=min/maxf[j]+s[j,i]f[i]=min/maxf[j]+s[j,i];(s[i,j]s[i,j]表示的是从j向i转移的时候，s[i,j]s[i,j]的每一项最多与calc(i)×calc(j)calc(i)×calc(j)相关，calc(i),calc(j)calc(i),calc(j)均不一定具有单调性，但j的选择区间是连续的)
斜率优化+CDQ分治或者斜率优化+Splay维护动态凸包
5.f[i]=min/maxf[j]+s[j,i]f[i]=min/maxf[j]+s[j,i];(s[i,j]s[i,j]表示的是从j向i转移的时候，s[i,j]s[i,j]满足四边形不等式，jj的选择区间是连续的)
决策单调性
剩下的，大概我并不会了...但是上述的DP都可以优化到O(nlogn)O(nlogn)之内。
决策单调性：
满足四边形不等式。
设j1<j2<i1<i2j1<j2<i1<i2
那么满足如果i1i1从j2j2转移，那么i2i2必定不可能从j1j1转移。这个东西，每道题证明不同，就不写了。
https://www.cnblogs.com/Winniechen/p/9218864.html
hdu3507printarticle（斜率dp优化）(代码片段)
ProblemDescriptionZerohasanoldprinterthatdoesn‘tworkwellsometimes.Asitisantique,hestillliketouseittoprintarticles.Butitistoooldtoworkforalongtimeanditwillcertainlywearandtear,soZerouseacosttoevaluatet 查看详情
hdu3507printarticle（斜率优化）(代码片段)
...连续输出一段，问输出所有数的总价值最小是多少思路：斜率优化，但我不知道为什么写成slop就不对，可怜我的斜率优化板子，又要该了，其他没什么，简单的推一下是下凸包，没什么其他的了代码：#include<set>#include<map&... 查看详情
hdu3507printarticle（斜率优化）(代码片段)
PrintArticleTimeLimit:9000/3000MS(Java/Others) MemoryLimit:131072/65536K(Java/Others)TotalSubmission(s):15536 AcceptedSubmission(s):4813ProblemDescription 查看详情
『土地征用landacquisition斜率优化dp』(代码片段)
斜率优化DP的综合运用，对斜率优化的新理解。详细介绍见『玩具装箱TOY斜率优化DP』土地征用LandAcquisition(USACO08MAR)DescriptionFarmerJohnisconsideringbuyingmorelandforthefarmandhashiseyeonN(1<=N<=50,000)additionalrectangularplots,eachwithintegerdimensions(1&l... 查看详情
hdu3480division（斜率优化）(代码片段)
...平方，求m个集合的价值总和最小思路：先给出TLE代码，斜率优化下次给出，转移方程dp[i][j]=min(dp[i][j],dp[i-1][k]+(a[j]-a[k+1])*(a[j]-a[k+1]));（ps：tzw竟然说买包烟十个人，九个人都会斜率优化过题，emmm）#include<bits/stdc++. 查看详情
poj1180斜率优化dp（单调队列）(代码片段)
BatchSchedulingTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 4347 Accepted: 1992DescriptionThereisasequenceofNjobstobeprocessedononemachine.Thejobsarenumberedfro 查看详情
bzoj1010[hnoi2008]玩具装箱toy（斜率优化第一题）(代码片段)
...gma的确让我看了好久思路：看了网上的很多题解，大概对斜率优化有了一点了解，发现斜率优化这种东西用在很多方面，比如在对凸壳的求解中，常用的kuangbin凸包模板中就有斜率优化的例子，对于单调队列的认识是基于某次被... 查看详情
poj1180batchscheduling-斜率优化dp(代码片段)
... 将等号左边看成纵坐标，$sumC_j$看成横坐标，$sumT_i$为斜率来进行斜率 查看详情
luogu3628特别行动队(斜率优化dp)(代码片段)
推出来式子以后斜率优化水过去就完事了1#include<cstdio>2#include<cstring>3#include<algorithm>4#include<vector>5#include<queue>6#include<cmath>7#defineinf0x3f3f3f3f8#defineLLlonglongint 查看详情
hdu3507：printarticle（斜率优化dp）(代码片段)
...与\(i,j\)两个变量有关，这种一般可以考虑分离变量然后斜率dp优化。(P 查看详情
luogu1010/bzoj3195玩具装箱(斜率优化dp)(代码片段)
推出来式子然后斜率优化水过去就完事了1#include<cstdio>2#include<cstring>3#include<algorithm>4#include<vector>5#include<queue>6#include<cmath>7#defineinf0x3f3f3f3f8#defineLLlonglongint 查看详情
任务安排2斜率优化dp(代码片段)
朴素n2n^2n2做法斜率优化DP：上面的朴素做法的式子是：f[i]=min(f[i],f[j]+t[i]∗(c[i]−c[j])+s∗(c[n]−c[j]))f[i]=min(f[i],f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j]))f[i]=min(f[i],f[j]+t[i]∗ 查看详情
hdu1300pearls（线性dp/斜率优化）(代码片段)
...第j个物品时的前缀时减pre[j-1]其他的就没有什么坑点了，斜率优化下次再更新代码：#include<bits/stdc++.h>usingnamespacestd;cons 查看详情
p2120[zjoi2007]仓库建设斜率优化dp(代码片段)
好题，这题是我理解的第一道斜率优化dp，自然要写一发题解。首先我们要写出普通的表达式，然后先用前缀和优化。然后呢？我们观察发现，x【i】是递增，而我们发现的斜率也是需要是递增的，然后就维护一个单调递增就行... 查看详情
1010:[hnoi2008]玩具装箱toy（斜率优化）(代码片段)
1010:[HNOI2008]玩具装箱toyTimeLimit: 1Sec MemoryLimit: 162MBSubmit: 12280 Solved: 5277[Submit][Status][Discuss]Description P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使 查看详情
bzoj4518[sdoi2016]征途(斜率优化dp)(代码片段)
我犯了sb错误然后调了1个小时......队列写错了斜率k递增，b取最小值，队列维护凸包即可f[0]的预处理好像有些奇怪？？？我把inf调大就过了？？？1#include<cstdio>2#include<algorithm>3#include<cstring>4#defineilinline5#definelllonglong6... 查看详情
斜率优化系列——训练记录(代码片段)
斜率优化训练记录前言斜率优化一般用于优化dp的转移，借着训练斜率优化的相关问题来提升一些DP思维。选择老学长留下的专题场来练手，由于该场题数较多，以及个人不太愿意长时间进行单一专题训练，因此开此文来记录断... 查看详情
[bzoj1767][ceoi2009]harbingers（树上斜率优化）(代码片段)
1767:[Ceoi2009]harbingers TimeLimit: 10Sec MemoryLimit: 64MBSubmit: 451 Solved: 120[Submit][Status][Discuss]Description 给定一颗树，树中每个结点有一个邮递员，每个邮递员要沿着唯 查看详情