设 $f[i]$ 表示前$i$个数划分完后的最小代价

$s[i]$ 表示前$i$ 个数的和

$f[i]=min(f[j]+(s[i]-s[j])^2+C)$

这个是典型的一维动态规划，而且它的$w(i,j)$是关于$s[i]*s[j]$的，因此我们想到要用斜率优化

$w(i,j) = (s[i]-s[j])^2+C$

然后我们容易证明

$w(i,j)+w(i+1,j+1) <= w(i+1,j) + w(i,j+1)$

则它满足四边形不等式

因此这个递推式子有决策单调性

然后我们化简一下式子

$f[i]-s[i]*s[i]-c=f[j]-2*s[j]*s[i]+s[j]*s[j]$

我们如果要用斜率优化，我们要满足$k$为一个关于$i$的东西且它得和一个关于$j$的东西相乘，$x$为一个关于$j$的东西且它得和一个关于$i$的东西相乘，$b$为一个关于$i$的东西，$y$为一个关于$j$的东西

那么我们可以得出

$x = s[j]$ $y = f[j] + s[j]*s[j]$ $k = 2*s[i]$ $b = f[i]-s[i]*s[i]-c$

这样我们的问题就变为如何让这个一次函数的截距最小

我们设$k < j < i$ 且$j$比$k$优

即$f[j]-2*s[j]*s[i]+s[j]*s[j]<f[k]-2*s[k]*s[i]+s[k]*s[k]$

化简可得$Y(j)-Y(k)/X(j)-X(k)<=2*s[i]$

那么只要满足这个式子就可以保证$j$比$k$优

假设有三个点$P(j1)$ $P(j2)$ $P(j3)$

$k1$为$P(j1)$ $P(j2)$的斜率

$k2$为$P(j3)$ $P(j2)$的斜率

假设$k2 < k1$ $k0$为$2*s[i]$

$k0 < k2 < k1$ $j1$优于$j2$优于$j3$ $k2 <= k0 < k1$ $j1$,$j3$优于$j2$ $k2 < k1 <= k0$ $j3$优于$j2$优于$j1$

可以发现这三个情况$j2$都是劣的

所以我们可以把它扔掉

所以我们要维护的点是在一个下凸包

然后他的斜率是单增的

然后我们最优的点就是最小的那个满足$k<=2s[i]$,然后他又有决策单调性

所以我们可以用一个单调队列，队头用$k<=2s[i]$去判，如果不行就扔，队尾维护一个下凸包就好

然后这个题就做完了

#include <bits/stdc++.h>
using namespace std;

const long long N = 5e5 + 10;

long long n, c, a[N], s[N], f[N], st[N], h, t;

void read(){
	for(long long i = 1;i <= n; i++){
		cin >> a[i];
		s[i] = s[i-1] + a[i]; 
	}
}

double X(long long i){
	return s[i];
}

double Y(long long i){
	return f[i] + s[i] * s[i];
}

double k(long long a,long long b){
	if(X(a)-X(b) == 0) return 1e18;
	return (Y(a)-Y(b))/(X(a)-X(b));
}

void compute(){
	memset(f,0,sizeof f);
	memset(st,0,sizeof st);
	h = t = 0;
	st[t++] = 0;
	for(long long i = 1;i <= n; i++){
		while(t - h > 1 && k(st[h],st[h+1]) <= s[i] * 2) h++;
		f[i] = f[st[h]] + (s[st[h]] - s[i]) * (s[st[h]] - s[i]) + c;
		while(t - h > 1 && k(st[t-1],st[t-2]) >= k(st[t-1],i)) t--;
		st[t++] = i;
	}
	cout << f[n] << '\n';
}

int main(){
	while(cin >> n >> c){
		read();
		compute();
	}
	return 0;
} 

不用斜率优化的做法：

$dp[i]$表示前i个数划分完的最小代价

首先我们可以发现对于所有的0 可以直接去掉 因为对答案没有任何贡献

剩下的部分每个数都至少为1

如果C=0 那么显然将它划分为n段是最优的

否则若将元素和分别为$s_i$和$s_j$的两端合并 需要$2*s_i*s_j$的代价，能节省C的花销

考虑暴力的dp转移中 $dp[j]$->$dp[i]$这条转移:

若在j~i中存在一个数k，使得 $2*sum[j到k]*sum[k+1到i]>=C$

则该转移一定不优于 $dp[j]$->$dp[k]$+$dp[k+1]$->$dp[i]$ 也就是说可以不考虑

因为“剩下的部分每个数都至少为1” 所以当$i-j>=2*\sqrt{C}$时，一定存在上文中的k

所以从$i-2*\sqrt{C}$到i转移即可

复杂度$O(n\sqrt{C})$

(如果倒着从$i$到$i-2*\sqrt{C}$转移能有更优的常数)

同时，该做法还可以推广到$k$次方的情况

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e18+1,mod=1e9+7;
int n,C,a[501000],dp[501000];
int sum[501000];
int b[501000],tot;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(cin>>n>>C){
		int tot=0;
		for(int i=1;i<=n;i++){
			dp[i]=inf;
			cin>>a[i];
			if(a[i]) b[++tot]=a[i];
		} 
		for(int i=1;i<=tot;i++){
			a[i]=b[i];
			sum[i]=sum[i-1]+a[i];
			for(int j=max(1ll,(int)(i-sqrt(2*C)-1));j<=i;j++){
				dp[i]=min(dp[i],dp[j-1]+(sum[i]-sum[j-1])*(sum[i]-sum[j-1])+C);
			}
		}
		cout<<dp[tot]<<"\n";
	}
	return 0;
}

进行一个式子的神秘的推。

大佬们太苣了，都会斜率优化，小蒟蒻不会怎么办？

受着

由于某OJ疑似数据范围没写西格玛，遂认为应该写线性做法，于是我认为转移一定存在某种规律使得转移集合可以被缩减，手动尺取了半天猜测了一个结论（果然还是基于人类智慧）。

对于转移到 $f_i$ 的每个 $f_j$，$j$ 单调不降。

考虑证明，从当前最优状态入手。（先贴个图）

假设 $f_i$ 的最优情况是由 $f_a$ 转移而来，$b$ 在 $a$ 的前一个位置，中间部分和为 $sum$，则有（方便起见，$a,b,i$ 同时表示这个位置和这个位置上的值,公式中 $c$ 都可以消掉，忽略）

化简得

接着考虑 $f_a->f_{i+1},f_b->f_{i+1}$ 的情况

(1): $f_a+(sum+i)^2$

(2): $f_b+(sum+i+a)^2$

令 (3)=(2)-(1): $f_b-f_a+a^2+2a\ sum + 2a\ i$

$f_b-f_a$ 取最小值,(3)=$2a\ i\ge0$

说明二式恒大于一式，无限向下递推该式可得如下结论：对于任意最优转移 $f_i->f_j$ 不存在最优转移 $f_a->f_b,a<i,b>j$。

故结论得证，代码真的很简单啊，复杂度基于zt的证明最劣 $O(n\sqrt c)$。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=5e5+17;
int n,c,f[N],q[N],a[N];
int sum(int l,int r){
	int res=(q[r]-q[l-1]);
	return res*res;
}int ans;
signed main(){
//	freopen("ex.in","r",stdin);
//	freopen("ex.ans","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int cnt;
	while(cin >> n){
		ans=0;cin>> c;
		for(int i=1;i<=n;i++){
			cin >> a[i];q[i]=q[i-1]+a[i];
		}
		int t=0; 
		for(int i=1;i<=n;i++){
			f[i]=1e14;int tmp;
			for(int j=t;j<i;j++){
				int re=f[j]+sum(j+1,i)+c;
				if(re<=f[i]){
					f[i]=re;tmp=j;
				}
			}t=tmp;
		}
		cout << f[n] << '\n';
	}
	return 0;
}

设 f[i] 表示前 i 个数划分完后的最小代价

$f[i]=min(f[j]+(sum[i]-sum[j])^2+C)$

$ans=f[n]$

复杂度 $O(n^2)$

考虑优化

对于 k < j < i ，假设选 j 比选 k 更优，则：

$f[j]+(sum[i]-sum[j])^2+C < f[k]+(sum[i]-sum[k])^2+C$

整理可得：

$\frac {f[j]+sum[j]^2 - (f[k]+sum[k]^2)}{sum[j]-sum[k]} < 2·sum[i]$

这样形成一个类似于求斜率的式子

令 $y_j=f[j]+sum[j]^2, x_j=sum[j]$ 则

$\frac{y_j-y_k}{x_j-x_k} < 2·sum[i]$

注意到不等式右边是递增的。（斜率优化的重要特点：单调）

令 g[k][j]表示刚刚的斜率式，即 g[k][j]=$\frac{y_j-y_k}{x_j-x_k}$

第一：如果 $g[k][j] < 2·sum[i]$，此时 $j$ 比 $k$ 优，则在后面 $i$ 更大时，$sum[i]$ 也更大，不等式肯定也成立，$j$ 同样比 $k$ 优，则 $k$ 点可以淘汰

第二：对于 $k < j < i < u$，如果 $g[j][i] < g[k][j]$，那么 $j$ 永远不可能成为最优解的决策，可以直接将它踢出我们的最优解集。为什么呢？

如果 $g[j][i] < 2·sum[u]$，那么就是说 $i$ 点要比 $j$ 点优，排除 $j$ 点。

如果 $g[j][i] ≥ 2·sum[u]$，那么 $j$ 点此时是比 $i$ 点要更优，但是同时 $g[k][j] > g[j][i] ≥ 2·sum[u]$。这说明还有 $k$ 点会比 $j$ 点更优，同样排除 $j$ 点。

所以相当于维护一个下凸壳，斜率在逐渐增大。用单调队列维护。