给定一个长度为n的序列,把它划分成m段,每段的和为 w i w_i wi 并给定一个参数p,要求最小化 ∑ i = 1 m ( w i + p ) 2 \sum_{i=1}^{m}(w_i+p)^2 ∑i=1m(wi+p)2
先把平方拆开,
a
n
s
=
m
p
2
+
2
p
∑
i
=
1
n
a
i
+
∑
i
=
1
m
w
i
2
ans=mp^2+2p\sum_{i=1}^na_i+\sum_{i=1}^mw_i^2
ans=mp2+2p∑i=1nai+∑i=1mwi2
前两项是定值,我们只需要最小化第三项即可
先写出dp方程,设
f
i
,
j
f_{i,j}
fi,j表示前 i 个位置划分成了 j 段的最小值
得到如下的转移方程
f
k
,
i
=
m
i
n
(
f
k
−
1
,
j
+
(
s
i
−
s
j
)
2
)
f_{k,i}=min(f_{k-1,j}+(s_i-s_j)^2)
fk,i=min(fk−1,j+(si−sj)2)
这个式子显然可以斜率优化,这样能做到复杂度
O
(
n
m
)
O(nm)
O(nm)
这个东西还是下凸的,可以wqs二分!!
我们二分一个 C C C,代表多划分一段,就要多出 C C C的额外花费,也就是在转移的时候多加上 C C C。记录最优解所需划分的段数,让段数小于等于 m m m即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const double eps=1e-9;
const ll inf=1ll<<40;
ll f[maxn],sum[maxn],p,sq[maxn];
int st[maxn],head,tail,n,m;
ll sqr(ll x)
{
return x*x;
}
double slope(int a,int b)
{
return 1.0*(f[b]-f[a]+sqr(sum[b])-sqr(sum[a]))/(1.0*(sum[b]-sum[a]));
}
int g[maxn];
void solve(ll mid)
{
head=tail=1; st[1]=0;
for(int i=1;i<=n;i++)
{
while(head<tail && slope(st[head],st[head+1])<2.0*sum[i]+eps) head++;
int j=st[head];
f[i]=f[j]+sqr(sum[i]-sum[j])+mid;
g[i]=g[j]+1;
while(head<tail && slope(st[tail-1],st[tail])+eps>slope(st[tail],i)) tail--;
st[++tail]=i;
}
}
int main()
{
freopen("divide.in","r",stdin);
freopen("divide.out","w",stdout);
scanf("%d%d%lld",&n,&m,&p);
for(int i=1;i<=n;i++)
{
ll x; scanf("%lld",&x);
sum[i]=sum[i-1]+x;
sq[i]=sum[i]*sum[i];
}
ll ans=2*p*sum[n]+m*p*p;
ll l=0,r=sq[n],res;
while(l<r)
{
ll mid=l+r>>1;
solve(mid);
if(g[n]>m) l=mid+1;
else res=f[n]-mid*m,r=mid;
}
printf("%lld",ans+res);
return 0;
}