斜率优化问题：
一些形如$dp(i)=min{dp(i),dp(j)+f(i)*A(j)}$的转移方程无法用单调队列优化。然而时间复杂度又不能$O(n^2)$。
这种情况下对于$dp(i)$，假如从$j$转移比从$k$转移更优，$j,k$需要满足一些条件。
我们通过整理这些条件可以将每个$i$抽象成坐标系中的一个点并用单调队列维护上凸/下凸包解决问题。
思路：
我们以HDU3507为例：
容易得出转移方程：$dp(i)=min{dp(i),dp(j)+[sum(i)-sum(j)]^{2}+M}$，其中$sum(i)=sum_{k=1}^{i}C_k$。
然后发现好像不太会优化……不如打个暴力走人
对于某个i，假设从j转移比从k转移更优，则我们有：
$dp(j)+[sum(i)-sum(j)]^{2}+M<dp(k)+[sum(i)-sum(k)]^{2}+M$
经过一些代数变换，我们得到：
$2 imes sum(i) imes[sum(k)-sum(j)]<dp(k)+sum(k)^{2}-[dp(j)+sum(j)^2]$
我们设j位于k前面，那么$sum(k)-sum(j)>0$，移项得到：
$2 imes sum(i)<frac{dp(k)+sum(k)^{2}-[dp(j)+sum(j)^2]}{sum(k)-sum(j)}$
发现右边就是过点$A(sum(k),dp(k)+sum(k)^{2})$和点$B(sum(j),dp(j)+sum(j)^{2})$的直线$AB$的斜率。
那么可以将每个$dp(i)$都按上面的方式转化成一个点放入坐标系中。
画图可以发现如果存在三个点形成上凸，那么中间那个点一定不是最优。
于是我们维护一些相邻两个点连线的斜率递增的点（下凸包）作为答案序列，
每次找到第一个与它右边的点连线的斜率$>2 imes sum(i)$的点，它就是当前转移的最优值。
由于$2 imes sum(i)$单调递增，我们可以用单调队列维护之，即每次删除答案点左边的所有点。
每个点只会入队出队一次，所以复杂度是线性的。
其他形式：
若$F_i =A_i x_j +B_i y_j$，则有$y_j = -frac{A_i }{B_i } x_j +frac{F_i }{B_i }$。
不难发现该式的几何意义为令一条斜率为$-frac{A_i }{B_i }$的直线依次经过每个点$(x_j , y_j)$，求最大截距。
则答案必然在上凸壳/下凸壳上，其余处理同上文。
该形式较为通用，可以避免分类讨论正负性。
代码：
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> using namespace std; #define MAXN 1000005 #define MAXM 500005 #define INF 0x7fffffff #define ll long long inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } ll N,M,C[MAXN],S[MAXN],q[MAXN],dp[MAXN]; inline ll getk(ll x1,ll x2) {return (dp[x2]+S[x2]*S[x2])-(dp[x1]+S[x1]*S[x1]);} int main(){ while(scanf("%d%d",&N,&M)!=EOF){ for(ll i=1;i<=N;i++) C[i]=read(),S[i]=S[i-1]+C[i]; ll head=1,tail=1; q[head]=0; for(ll i=1;i<=N;i++){ while(head<tail && getk(q[head],q[head+1])<=2*S[i]*(S[q[head+1]]-S[q[head]])) head++; dp[i]=dp[q[head]]+(S[i]-S[q[head]])*(S[i]-S[q[head]])+M; while(head<tail && getk(q[tail-1],q[tail])*(S[i]-S[q[tail]])>=getk(q[tail],i)*(S[q[tail]]-S[q[tail-1]])) tail--; q[++tail]=i; } printf("%lld ",dp[N]); } return 0; }