啊，这个是我很早很早之前就想搞懂的知识点了emmm可是一直没有解决。今天总算有机会了！

我今天打算做P3195，把这道板子肝出来。

题意：

你有一个序列，你可以任意地将其中的i-j项合并成一组。并且对于每一组，代价为 $(x-L)^2$。其中， $x=j-i+\sum_{k=i}^j C_k$，L为常亮。求最小代价。

$N^2$ 解法

我们让 $s[i]=\sum_{j=1}^i+i$(即前缀和+i)，可以发现状态转移方程可以变成：

$$f[i]=min_{j=0}^{i-1}(f[j]+(s[i]-s[j]-1-l)^2);$$

于是愉快 $N^2$暴力，吸氧后70分。

午餐

午餐和Atalod一起吃，吃了金拱门。虽然等了很久，但是我们聊了一会儿斜率优化。

斜优数论证明

对于上面的这个方程，我们假设对于一个我们将要求的i。有两个j,分别是 $j_1,j_2$,我们假设 $j_1$的解更小(更优秀)。

$$f[j_1]+(s_i-s_{j_1}-1-l)^2\leq f[j_2]+(s_i-s_{j_2}-1-l)^2$$

拆开：

$$f[j_1]+s_i^2-2*s_i*(s_{j_1}-1-l)+(s_{j_1}-1-l)^2\leq f[j_2]+s_i^2-2*s_i*(s_{j_2}-1-l)+(s_{j_2}-1-l)^2$$

化简：

$$-2*s_i*(s_{j_1}-1-l)+2*s_i*(s_{j_2}-1-l)\leq -f[j_1]+f[j_2]+(s_{j_2}-1-l)^2-(s_{j_1}-1-l)^2$$

再化简：

$$2*s_i*(s_{j_2}-s_{j_1})\leq -f[j_1]+f[j_2]+(s_{j_2}-1-l)^2-(s_{j_1}-1-l)^2$$

再再化简：

$$2*s_i\leq \frac{-f[j_1]+f[j_2]+(s_{j_2}-1-l)^2-(s_{j_1}-1-l)^2}{(s_{j_2}-s_{j_1})}$$

经过我们的推导，我们发现，只要任意的 $j_1,j_2$满足上式子， $j_1$就更优秀，也就是 $j_1$更小。 接下来，我们发现，我们可以根据下标与下标所对应的值建立一个个散点。

根据我们的推论， $2*s_i$作为斜率，我们应当找到某个j作为转移决策点，而且这个转移决策点需要保证让 $f[i]$最小。

借用上面的一个公式： $$f[i]=f[j]+(s[i]-s[j]-1-l)^2;$$

$f[j]$就是高度, $(s[i]-s[j]-1-l)^2$是斜率

然后发现我们要做的只是拿一条斜率为 $2*s[i]$的直线去逼近它，找到第一个决策点。

我们可以发现，只有这些散点中能够成下凸壳的那些点才有可能成为决策点。

然后队列或者栈维护凸壳。

而这个方程，前缀和单增，y=x单增，所以 $s_i$单增，所以斜率单增，满足斜率单调性。

对于有决策单调性的方程，决策点一定会会后移或不动，不可能前移。每个点是最多进队一次，出队一次。复杂度 $O(n)$

对于没有决策单调性的点，决策点可能乱跳。每个点进栈出栈最多一次。对于每一个i，在凸壳上二分即可找到决策点。复杂度 $O(n log n)$

此题吸氧70分的 $O(n^2)$做法

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=52505;
int f[N],a[N],s[N];
int q[N],be,ed;
int n,l;
int X(int j){
    return s[j];
}
int Y(int j){
    return f[j]+(s[j]+l)*(s[j]+l);
}
long double slope(int i,int j){
    return (long double)(Y(j)-Y(i))/(X(j)-X(i));
}
signed main(){
    cin>>n>>l;
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
        s[i]=s[i-1]+a[i]+1;
    }
    q[++ed]=1;
    for(int i=1;i<=n;++i){
        f[i]=0x3f3f3f3f3f3f3f3f;
        for(int j=0;j<i;++j)
            f[i]=min(f[i],f[j]+(s[i]-s[j]-1-l)*(s[i]-s[j]-1-l));
    }
    cout<<f[n];
}

斜优 $O(n)$做法

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=52505;
int f[N],a[N],s[N];
int q[N],be,ed;
int n,l;
int X(int j){
    return s[j];
}
int Y(int j){
    return f[j]+(s[j]+l)*(s[j]+l);
}
long double slope(int i,int j){
    return (long double)(Y(j)-Y(i))/(X(j)-X(i));
}
signed main(){
    cin>>n>>l;
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
        s[i]=s[i-1]+a[i]+1;
    }
    q[++ed]=1;
    for(int i=1;i<=n;++i){
//      f[i]=0x3f3f3f3f3f3f3f3f;
//      for(int j=0;j<i;++j)
//          f[i]=min(f[i],f[j]+(s[i]-s[j]-1-l)*(s[i]-s[j]-1-l));
        while(be<=ed&&slope(q[be],q[be+1])<=2*s[i])
            be++;
        f[i]=f[q[be]]+(s[i]-s[q[be]]-1-l)*(s[i]-s[q[be]]-1-l);
        while(be<=ed&&slope(q[ed-1],q[ed])>=slope(q[ed-1],i))
            ed--;
        q[++ed]=i;
    }
    cout<<f[n];
}