题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3156
裸的斜率优化，记一下以后复习用吧。
要直接dp很明显应该要倒着dp，很不爽，先把它倒过来。
令$sum[j]=sum_{i=1}^ji$，于是我们首先推出这样一个方程$$f[i]=min{f[j]+sum[i-1]-sum[j]-(i-j-1)*j+a[i]}$$
这样dp复杂度是$O(n^{2})$的，考虑斜率优化。
设$k>j$,且$k$优于$j$，则有$$f[k]+sum[i-1]-sum[k]-(i-k-1)*k+a[i]<f[j]+sum[i-1]-sum[j]-(i-j-1)*j+a[i]$$
整理得$$f[k]-f[j]-(sum[k]-sum[j])+k^{2}-j^{2}+k-j<i*(k-j)$$
把$k-j$直接除过去，得$slope(k,j)<i$，因为$i$是单调递增的，所以只要有一次$k$优于$j$，$k$永远都优于$j$，直接把$j$给T掉就好了。
这样就可以用单调队列来维护。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 typedef long long ll; 6 const ll INF=1LL<<62; 7 int inline readint(){ 8 int Num;char ch; 9 while((ch=getchar())<'0'||ch>'9');Num=ch-'0'; 10 while((ch=getchar())>='0'&&ch<='9') Num=Num*10+ch-'0'; 11 return Num; 12 } 13 int n,data[1000010],a[1000010]; 14 ll f[1000010],sum[1000010]; 15 int q[1000010],h,t; 16 double slope(int k,int j){ 17 return (double)(f[k]-f[j]-(sum[k]-sum[j])+(ll)k*k-(ll)j*j+k-j)/(k-j); 18 } 19 int main(){ 20 n=readint(); 21 for(int i=1;i<=n;i++) data[i]=readint(); 22 for(int i=1;i<=n;i++){ 23 a[i]=data[n-i+1]; 24 sum[i]=sum[i-1]+i; 25 } 26 h=t=1; 27 f[1]=a[1]; 28 q[1]=1; 29 ll ans=f[1]+sum[n]-sum[1]-n+1; 30 for(int i=2;i<=n;i++){ 31 while(h<t&&slope(q[h+1],q[h])<=i) h++; 32 f[i]=f[q[h]]+sum[i-1]-sum[q[h]]-(ll)(i-q[h]-1)*q[h]+a[i]; 33 ans=min(ans,f[i]+sum[n]-sum[i]-(ll)(n-i)*i); 34 while(h<t&&slope(q[t],q[t-1])>=slope(i,q[t])) t--; 35 q[++t]=i; 36 } 37 printf("%lld",ans); 38 return 0; 39 }