题解
可以发现原方程为:
$$f[i]=min_{0<=j<i} (f[j]+((i+sum[i]-L-1)-(sum[j]+j))^2)$$
设$a[i]=i+sum[i]-L-1,b[j]=sum[j]+j$,
则$f[i]=min_{0<=j<i} (f[j]+(a[i]-b[j])^2)=min_{0<=j<i} (f[j]+a[i]^2+b[j]^2-2a[i]b[j])$
再设$x[i]=b[j],y[j]=f[j]+b[j]^2$
则可以发现a和x都单调递增，所以斜率是单调递减的。用单调队列维护凸壳，每次从队首不断出队以找出最优决策。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<bits/stdc++.h>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;
inline int read()
{
int data=0, w=1;
char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1, ch=getchar();
while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar();
return data*w;
}
const int maxn(50010);
typedef long long ll;
int n, L, head, tail, q[maxn];
long long f[maxn], sum[maxn];
#define a(i) (sum[i]+(i))
#define b(i) (a(i)+L+1)
inline double sqr(long long x) { return ((double)x)*x; }
inline long long sqrl(long long x) { return x*x; }
inline double x(int i) { return (double)b(i); }
inline double y(int i) { return f[i]+sqr(b(i)); }
inline double slope(int i, int j) { return (y(i)-y(j))/(x(i)-x(j)); }
int main()
{
n=read(); L=read();
for(RG int i=1;i<=n;i++) sum[i]=sum[i-1]+read();
head=tail=1;
for(RG int i=1;i<=n;i++)
{
while(head^tail&&slope(q[head], q[head+1])<2*a(i)) ++head;
f[i]+=f[q[head]]+sqrl(a(i)-b(q[head]));
while(head^tail&&slope(q[tail-1], i)<slope(q[tail-1], q[tail])) --tail;
q[++tail]=i;
}
printf("%lld\n", f[n]);
return 0;
}
|