DP优化技巧-斜率优化（基础版）
基本思路：
1.寻找出暴力DP转移方程式。例子：f[i]=min{f[j]+v[i]+v[j]+val(i,j)}
2.将方程式写成y=kx+b的形式，其中b为与i相关的项，y为与j相关的项，kx对应的是val(i,j)项，其中x对应的的是与j相关的，k对应的是与i相关的以及常数。例子：假设有转移方程f[i]=min{f[i],f[j]+sum[i]*sum[i]+sum[j]*sum[j]+2*sum[i]*sum[j]+C}(C为常数) 那么可以得到f[j]+sum[j]*sum[j]=2*sum[j]*sum[i]-f[i]+sum[i]*sum[i]+C 其中f[j]+sum[j]*sum[j]为y项，sum[j]对应x项，2*sum[i]对应k项，-f[i]+sum[i]*sum[i]+C为b项。
3.建立单调队列进行维护凸包，凸包的知识在此挖个坑，届时会补上（不一定:P 而单调队列的push操作里的去除队尾的依据为新加入元素没有与队尾、队尾前一个元素组成一个下凸壳。如果队尾只有或只剩一个元素，则退出此操作。
4.在单调队列中进行二分，根据凸壳的知识，选择合适的点，对f[i]进行普通赋值。
易错点/注意到：
1.容易将一些无用的状态忽略，而没有对其赋最大/最小值，输入DP通病。
2.要搞清楚自己的k的符号，假如最终化简方程式形式为：b=y-kx，则求出来的k应该取相反数。
3.要根据k的值维护上凸包or下凸包。
4.注意单调队列的初始化。
5.注意队列里只有1or0个元素时，不应该进行判定操作，而是直接加入or进行其他操作。
6.多回头进行公式以及各个函数内容的检查与重算。
例题:
1.洛谷P4072 [SDOI2016] 征途
核心转移方程式：f[i][j]=f[i-1][k]+((sum[j]-sum[k])*m-sum[n])*((sum[j]-sum[k])*m-sum[n])
改写方程式：f[i][j]-(m*sum[j]-sum[n])*(m*sum[j]-sum[n])=(f[i-1][k]+m*m*sum[k]*sum[k]+2*m*sum[j]*sum[n])+2*m*m*sum[j]*sum[k]
补充说明：核心转移方程式中的k取值范围为：1<=k<j，改写方程式中的k为使f[i][j]最小的下标，经过单调队列优化得到
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
long long f[3010][3010],sum[3010];
double qy(int i,int j){double ans=f[i][j]+m*m*sum[j]*sum[j]+2*m*sum[j]*sum[n];return ans;}
double qx(int j){double ans=sum[j];return ans;}
double qk(int i,int j,int k,int l){return (qy(i,j)-qy(k,l))/(qx(j)-qx(l));}
long long val(int j,int i){return ((sum[i]-sum[j])*m-sum[n])*((sum[i]-sum[j])*m-sum[n]);}
struct que{
int l,r,a[200010];
void memsets(){l=1;r=0;}
int size(){return r-l+1;}
int front(){return a[l];}
void pop(){l++;}
void push(int i,int x){
while (size()>=2&&(qk(i,a[r-1],i,a[r])>=qk(i,a[r],i,x))==true) r--;
a[++r]=x;
}
}q;
long long a[3010];
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){scanf("%lld",&a[i]);sum[i]=sum[i-1]+a[i];}
for (int i=1;i<=n;i++) f[1][i]=val(0,i);
for (int i=2;i<=m;i++){
q.memsets();
for (int j=1;j<i;j++){
f[i][j]=1e18;
}
for (int j=i;j<=n;j++){
q.push(i-1,j-1);
long double k=2.0*m*m*sum[j];
while (q.size()>=2&&k>=qk(i-1,q.a[q.l],i-1,q.a[q.l+1])) q.pop();
int o=q.front();
f[i][j]=f[i-1][o]+val(o,j);
}
}
printf("%lld",f[m][n]/m);
return 0;
}
2.洛谷P3195 [HNOI2008] 玩具装箱
核心转移方程式：f[i][j]=min(j<i){f[j]+(sum[i]-sum[j]+i-j-1-L)*(sum[i]-sum[j]+i-j-1-L)}
令s[i]=sum[i]+i,L1=L+1，得到：f[i]=min(j<i){f[j]+(s[i]-s[j]-L1)*(s[i]-s[j]-L1)}
改写方程式：f[i]-(s[i]-L1)*(s[i]-L1)=min(j<i){f[j]+s[j]*s[j]+2*s[j]*(L1-s[i])}
补充说明：j与上面的k类似
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
long long l,l1,a[100010],f[100010],sum[100010],s[100010];
double qy(int i){return 1.0*f[i]+1.0*s[i]*s[i];}
double qx(int i){return 1.0*s[i];}
double qk(int i,int j){double ans=1.0*(1.0*qy(i)-1.0*qy(j))/(1.0*qx(i)-1.0*qx(j));return ans;}
bool cmp(int i,int j,int k){return qk(i,j)<=qk(j,k);}
struct que{
int l,r,b[200010];
void memsets(){l=1;r=0;memset(b,0,sizeof(b));}
int front(){return b[l];}
void pop(){l++;}
bool empty(){return r-l+1==0;}
int size(){return r-l+1;}
void push(int x){
while (size()>=2&&cmp(x,b[r],b[r-1])==true) --r;
b[++r]=x;
}
}q;
int main(){
scanf("%d%lld",&n,&l);l1=l+1;q.memsets();
for (int i=1;i<=n;i++){scanf("%lld",&a[i]);sum[i]=sum[i-1]+a[i];s[i]=sum[i]+i;}
// for (int i=1;i<=n;i++) printf("i=%d sum[%d]=%lld s[%d]=%lld\n",i,i,sum[i],i,s[i]);
for (int i=1;i<=n;i++){
q.push(i-1);
if (i==1){f[i]=(a[1]-l)*(a[1]-l);}
else{
long long k=2*(s[i]-l1);
while (q.size()>=2&&k>1.0*(qy(q.b[q.l+1])-qy(q.b[q.l]))/(qx(q.b[q.l+1])-qx(q.b[q.l]))){
q.pop();
}
int j=q.front();f[i]=f[j]+(s[i]-s[j]-l1)*(s[i]-s[j]-l1);
}
}
printf("%lld",f[n]);
return 0;
}```
***