Orz CYC帮我纠正了个错误。斜率优化并不需要决策单调性,只需要斜率式右边的式子单调就可以了
codevs也有这题,伪·双倍经验233
首先朴素DP方程很容易看出:f[i]=min(f[j]+(i-j-1+sum[i]-sum[j]-L)^2);
于是设g[i]=i+sum[i]
g[j]=j+sum[j]
c=1+L
则f[i]=min(f[j]+(g[i]-g[j]-c)^2)
方法一:决策单调性优化
证明决策单调性,假设 j 比 k 优
f[j]+(g[i]-g[j]-c)^2<f[k]+(g[i]-g[k]-c)^2
证明f[j]+(g[x]-g[j]-c)^2<f[k]+(g[x]-g[k]-c)^2
f[j]+(g[i]+y-g[j]-c)^2<f[k]+(g[i]+y-g[k]-c)^2
f[j]+(g[i]-g[j]-c)^2-2*y*(g[i]-g[j]-c)<f[k]+(g[i]-g[k]-c)^2-2*y*(g[i]-g[k]-c)
g[j]>g[k]
所以当 j > k 时,j 比 k 优,则 j 一直比 k 优。
于是就可以决策单调性优化了,分治优化超妙的
方法二:斜率优化
f[j]+(g[i]-g[j]-c)^2<f[k]+(g[i]-g[k]-c)^2
f[j]-2*g[i]*(g[j]+c)+(g[j]+c)^2<f[k]-2*g[i]*(g[k]+c)+(g[k]+c)^2
(f[j]+(g[j]+c)^2-f[k]-(g[k]+c)^2)/(2*(g[k]-g[j]))<g[i]
所以斜率是递增的,维护个下凸包
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn=;
int l,r;
ll n,L,sum[maxn],g[maxn],q[maxn],f[maxn];
void read(ll &k)
{
int f=;k=;char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(c<=''&&c>='')k=k*+c-'',c=getchar();
k*=f;
}
ll sqr(ll x){return x*x;}
ll xl(int j,int k){return (f[j]+sqr(g[j]++L)-f[k]-sqr(g[k]++L))/(*(g[j]-g[k]));}
int main()
{
read(n);read(L);
for(int i=;i<=n;i++)
read(sum[i]),sum[i]+=sum[i-];
for(int i=;i<=n;i++)
{
g[i]=i+sum[i];
while(l<r&&xl(q[l],q[l+])<g[i])l++;
f[i]=f[q[l]]+sqr(g[i]-g[q[l]]--L);
while(l<r&&xl(q[r],q[r-])>xl(i,q[r]))r--;
q[++r]=i;
}
printf("%lld\n",f[n]);
}