【总结】斜率优化DP

如果满足上式 ，则 \(j 且 \(j\) 优于 \(k\)。

记住上面推式子的步骤，现在记不住等会儿再重复这个步骤推十几个式子也能记住的OwO

充要条件是什么鬼呀，我不会证呀QAQ

好了，接下来是斜率优化的重点部分——

在义务教育阶段，学生学习了一次函数，它的几何意义表示为一条直线，一次项的系数就是直线的斜率，只不过当直线与 \(x\) 轴垂直的时候无法表示。虽然没有明确给出斜率这个名词，但实际上思想已经渗透到其中。

直线对 \(x\) 轴的倾斜角 \(\alpha\) 的正切值 \(\tan\alpha\) 称为该直线的“斜率”，并记作 \(k\) ，公式为 \(k=\tan\alpha\)。

即 \(k=\tan\alpha=\dfrac{\Delta y}{\Delta x}=\dfrac{y_2-y_1}{x_2-x_1}\) 或 \(\dfrac{y_1-y_2}{x_1-x_2}\) 。

——选自 斜率_百度百科

XSC062看完了百度百科表示你TM在说些啥是不是欺负我六年义务教育的小学生恍然大悟

上面推出来的那个关于 \(j\) 和 \(k\) 的DP式，不就是求两个点 \((f_j+{s_j}^2,2\times s_j)\) 和 \((f_j+{s_k}^2,2\times s_k)\) 连成一条线之后的坡度吗！

本文后面的部分，\(x\) 的含义会在“点\((f_x+{s_x}^2,2\times s_x)\)”和“\(x\)这个下标”之间漂浮，请根据语境识别~

随后XSC062边打瞌睡边听GM讲课（特异功能），勉强算是明白了中心意思：

如图，假设有三个点 \(A,B,C\)，以及 \(B,A\) 的斜率 \(k_1\)，\(C,B\) 的斜率 \(k_2\)。

我们暂且把这个向外凸起的奇怪玩意儿称为一个上凸。

回到前面的我们得到的那个结论：

\[\dfrac{(f_j+{s_j}^2)-(f_k+{s_k}^2)}{(2\times s_j)-(2\times s_k)}

如果满足上式 ，则 \(j 且 \(j\) 优于 \(k\)。

简单记忆为：

• 若点 \(x,y\) 的斜率比 \(s_i\) 小，则 \(x 且 \(x\) 优于 \(y\) 。
• 反之，若点 \(x,y\) 的斜率比 \(s_i\) 大，则 \(y 且 \(y\) 优于 \(x\)。

将 \(A,B\) 代入，我们得知：

1. 若 \(k_1\leqslant s_i\)，则 \(B\) 优于 \(A\)。
2. 若 \(k_1>s_i\)，则 \(A\) 优于 \(B\)。
3. 若 \(k_2\leqslant s_i\)，则 \(C\) 优于 \(B\)。
4. 若 \(k_2>s_i\)，则 \(B\) 优于 \(C\)。（人类的本质……

因为斜率=倾斜度=竖得有多高，明显 \(k_1>k_2\)。所以针对一个大小关系，\(k_1\) 和 \(k_2\) 之间只有可能有：

1. \(s_i，此时 \(B\) 优于 \(C\)，\(A\) 优于 \(B\)，\(A\) 为最优解。
2. \(k_2，此时 \(C\) 优于 \(B\)，\(A\) 优于 \(B\)，\(A,C\) 为最优解。
3. \(k_2，此时 \(C\) 优于 \(B\)，\(B\) 优于 \(A\)，\(C\) 为最优解。

发现了吗？\(B\) 永远都不可能是最优解。（可怜。。。

所以如果我们要维护一个最优解的序列，就可以不要 \(B\) 了。

那么，这个最优解序列里肯定已经不会存在“上凸”了。

如果是这样的“下凸”呢？

\(k_1\) 为 \(B,A\) 的斜率，\(k_2\) 为 \(C,B\) 的斜率。

将 \(A,B\) 代入，我们得知：

1. 若 \(k_1\leqslant s_i\)，则 \(B\) 优于 \(A\)。
2. 若 \(k_1>s_i\)，则 \(A\) 优于 \(B\)。
3. 若 \(k_2\leqslant s_i\)，则 \(C\) 优于 \(B\)。
4. 若 \(k_2>s_i\)，则 \(B\) 优于 \(C\)。

明显 \(k_1。所以 \(k_1\) 和 \(k_2\) 之间只有可能有：

1. \(s_i，此时 \(B\) 优于 \(C\)，\(A\) 优于 \(B\)，\(A\) 为最优解。
2. \(k_1，此时 \(B\) 优于 \(C\)，\(B\) 优于 \(A\)，\(B\) 为最优解。
3. \(k_1，此时 \(C\) 优于 \(B\)，\(B\) 优于 \(A\)，\(C\) 为最优解。

所以，在下凸的情况中，三个点都有可能是最优解，都需要保留。

现在呢，所有上凸都被去掉了，只剩下凸，所以大概最后的最优解序列就长这个样子：

好丑

反过来看就是lifan的脑袋了

观察发现，斜率是从左往右递增的。

所以，我们考虑用单调队列来当这个“最优解序列”。

维护队头

即保证队头元素为最优解。

设队头为 \(q_l\)。

如果 \(q_{l+1}\) 与 \(q_l\) 形成的斜率 \(\leqslant s_i\)，根据上面推出来的玩意儿，得到 \(q_{l+1}\) 优于 \(q_l\)。

那还要 \(q_l\) 干啥，直接 l++。

更新DP值

\(f_i=f_{q_l}-2\times s_i\times s_{q_l}+{s_{q_l}}^2+{s_i}^2+M\)

维护队尾

即保证里面塞的点相邻两个的斜率递增。（听起来好怪。。。

设队尾为 \(q_r\)，我们要往最优解队列里push一个 \(i\) 。

若队尾两个点 \(q_r,q_{r-1}\) 形成的斜率比 \(i,q_r\) 形成的斜率大，那么push(i)后，整个队列的斜率就不再单调递增，所以此时要将r--。（因为中讲到的 \(i\) 必须入队，只能委屈一下 \(q_r\) 了）

注意事项

众所周知，斜率是个浮点数。为了避免损失精度造成的一些惨案，我们交叉相乘，将分子、分母分开处理。

以及时刻都要保证队列中至少有两个点，因为要访问 \(q_l,q_{l+1}\) 和 \(q_r,q_{r-1}\)。

Code

#include
const int maxn=5e5+5;
int n,m,l,r;
int f[maxn],c[maxn],q[maxn];
int getDP(int i,int j){
	return f[j]+m+(c[i]-c[j])*(c[i]-c[j]);
}
int getup(int j,int k){
	//计算分子的值
	return f[j]+c[j]*c[j]-f[k]-c[k]*c[k];
}
int getdown(int j,int k){
	//计算分母的值
	return (c[j]-c[k])*2;
}
int main(){
	while(~scanf("%d%d",&n,&m)){
		l=r=1;
		//经验表明，凡是涉及到前缀和的单调队列都必须先在队列中push(0)，因为sum[0]这个玩意
		for(int i=1;i<=n;++i){
			scanf("%d",&c[i]);
			//懒得开前缀和数组，c自给自足
			c[i]+=c[i-1];
			//维护队头
			//l

for(int i=1;i<=n;++i){
	scanf("%lld",&c[i]);
	c[i]+=c[i-1];
}
for(int i=1;i<=n;++i)
	c[i]+=i;

#include
#define int long long
const int maxn=5e4+5;
const int inf=0x3f3f3f3f;
int n,L,l,r;
int f[maxn],c[maxn],q[maxn];
int getDP(int i,int j){
	return f[j]+(c[i]-c[j]-L)*(c[i]-c[j]-L);
}
int getup(int j,int k){
	return f[j]-f[k]+2*c[j]*L-2*c[k]*L+c[j]*c[j]-c[k]*c[k];
}
int getdown(int j,int k){
	return c[j]-c[k]<<1;
}
signed main(){
	scanf("%lld%lld",&n,&L);
	++L;
	l=r=1;
	for(int i=1;i<=n;++i){
		scanf("%lld",&c[i]);
		c[i]+=c[i-1];
	}
	for(int i=1;i<=n;++i){
		c[i]+=i;
		while(l

#include
#include
const int maxn=5005;
int n,s,ans=1<<30;
int f[maxn][maxn];
int t[maxn],c[maxn];
int min(int x,int y){return x

#include
#include
#define int long long
const int maxn=5005;
int n,s;
int t[maxn],c[maxn],f[maxn];
int min(int x,int y){return x

#include
#define int long long
const int maxn=300005;
int n,s,l,r;
int t[maxn],c[maxn],q[maxn],f[maxn];
int getDP(int i,int j){
	return f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j]);
}
int getup(int j,int k){
	return f[j]-f[k]-s*c[j]+s*c[k];
}
int getdown(int j,int k){
	return c[j]-c[k];
}
signed main(){
	scanf("%lld%lld",&n,&s);
	l=r=1;
	for(int i=1;i<=n;++i){
		scanf("%lld%lld",&t[i],&c[i]);
		t[i]+=t[i-1];
		c[i]+=c[i-1];
	}
	for(int i=1;i<=n;++i){
		while(l

#include
#include
#define int long long
const int maxn=300005;
int n,s,l,r;
int t[maxn],c[maxn],q[maxn],f[maxn];
int getDP(int i,int j){
	return f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j]);
}
int getup(int j,int k){
	return f[j]-f[k]-s*c[j]+s*c[k];
}
int getdown(int j,int k){
	return c[j]-c[k];
}
int BinarySearch(int val){
    if(l==r)return q[l];
    int L=l,R=r;
    //二分整个单调队列
    while(L>1;
        if(getup(q[mid+1],q[mid])<=val*getdown(q[mid+1],q[mid]))
            L=mid+1;
        else R=mid;
    }
    return q[L];
}
signed main(){
	scanf("%lld%lld",&n,&s);
	l=r=1;
	for(int i=1;i<=n;++i){
		scanf("%lld%lld",&t[i],&c[i]);
		t[i]+=t[i-1];
		c[i]+=c[i-1];
	}
	for(int i=1;i<=n;++i){
		int pos=BinarySearch(t[i]);
		f[i]=getDP(i,pos);
		while(l

struct land{
    int w,l;
    bool operator<(const land q)const{
        return w==q.w?l>q.l:w>q.w;
    }
}a[maxn];

...

sort(a+1,a+n+1);
for(int i=1;i<=n;++i){
    if(a[i].l>a[cnt].l)
        a[++cnt]=a[i];
}

#include
#include
using std::sort;
#define int long long
const int maxn=5e4+5;
struct land{
    int w,l;
    bool operator<(const land q)const{
        return w==q.w?l>q.l:w>q.w;
    }
}a[maxn];
int n,cnt,l,r;
int q[maxn],f[maxn];
int getup(int j,int k){return f[j]-f[k];}
int getdown(int j,int k){return a[k+1].w-a[j+1].w;}
int getDP(int i,int j){return f[j]+a[j+1].w*a[i].l;}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)
        scanf("%lld%lld",&a[i].w,&a[i].l);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i){
        if(a[i].l>a[cnt].l)
            a[++cnt]=a[i];
    }
    n=cnt;
    l=r=1;
    for(int i=1;i<=n;++i){
		while(l

#include
#define int long long
const int maxn=1e6+5;
int n,l,r;
int a[maxn],b[maxn];
int f[maxn],x[maxn],p[maxn],c[maxn],q[maxn];
int getDP(int i,int j){
	return f[j]+(a[i]-a[j])*x[i]-(b[i]-b[j])+c[i];
}
int getup(int j,int k){
	return f[j]-f[k]+b[j]-b[k];
}
int getdown(int j,int k){
	return a[j]-a[k];
}
signed main(){
	scanf("%lld",&n);
	l=r=1;
	for(int i=1;i<=n;++i){
		scanf("%lld%lld%lld",&x[i],&p[i],&c[i]);
		a[i]=a[i-1]+p[i];
		b[i]=b[i-1]+x[i]*p[i];
		while(l

#include
#include
#include
using std::sort;
#define int long long
const int maxn=1e5+5;
int n,m,p,h,t,l,r;
int f[105][maxn];
int a[maxn],s[maxn],d[maxn],q[maxn];
int getDP(int i,int j,int k){
	return f[i-1][k]+j*a[j]-k*a[j]-s[j]+s[k];
}
int getup(int i,int x,int y){
	return f[i-1][x]+s[x]-f[i-1][y]-s[y];
}
int getdown(int x,int y){
	return x-y;
}
signed main(){
    memset(f,0x3f,sizeof(f));
	scanf("%lld%lld%lld",&n,&m,&p);
	for(int i=2;i<=n;++i){
		scanf("%lld",&d[i]);
        d[i]+=d[i-1];
    }
	for(int i=1;i<=m;++i){
        scanf("%lld%lld",&h,&t);
		a[i]=t-d[h];
	}
    sort(a+1,a+m+1);
    for(int i=1;i<=m;++i)
        s[i]=s[i-1]+a[i];
    f[0][0]=0;
    for(int i=1;i<=p;++i){
	    l=r=1;
        for(int j=1;j<=m;++j){
            while(l

#include
#include
#define int long long
const int maxn=3005;
int f[maxn][maxn];
int a[maxn],q[maxn];
int n,m,l,r,ans=1e18;
int getDP(int i,int j,int k){
	return f[k-1][j]+(a[i]-a[j])*(a[i]-a[j]);
}
int getup(int j,int k,int i){
	return f[i-1][j]-f[i-1][k]+a[j]*a[j]-a[k]*a[k];
}
int getdown(int j,int k){
	return a[j]-a[k]<<1;
}
int min(int x,int y){return x

#include
#include
//不用vector会MLE（但vector难调到像吃了shit一样
using namespace std;
#define int long long
#define top q[x].size()-1
const int maxn=1e5+5;
const int maxm=1e4+5;
int n;
vectorq[maxm];
int f[maxn],s[maxn];
int cnt[maxn],tot[maxm];
int getDP(int i,int j){
	return f[j-1]+(cnt[i]-cnt[j]+1)*(cnt[i]-cnt[j]+1)*s[i];
}
int getup(int j,int k){
	return f[j-1]-f[k-1]+s[j]*cnt[j]*cnt[j]-s[k]*cnt[k]*cnt[k]-2*s[j]*cnt[j]+2*s[k]*cnt[k];
}
int getdown(int j,int k){
	return cnt[j]-cnt[k];
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;++i){
		scanf("%lld",&s[i]);
		cnt[i]=++tot[s[i]];
    }
    for(int i=1;i<=n;++i){
        int x=s[i];
		while(q[x].size()>=2&&getup(q[x][top-1],i)*getdown(q[x][top-1],q[x][top])>=getup(q[x][top-1],q[x][top])*getdown(q[x][top-1],i))
            q[x].pop_back();
		q[x].push_back(i);
		while(q[x].size()>=2&&getDP(i,q[x][top])<=getDP(i,q[x][top-1]))
            q[x].pop_back();
		f[i]=getDP(i,q[x][top]);
	}
	printf("%lld",f[n]);
	return 0;
}