题意
求将一个长为(n)的序列(每个数为(c_i))分为很多段，每段((i)~(j))的花费是(displaystyle (j-i+sum_{k=i}^{j}c_k-L)^2)，求最小的花费。
((n<=50000))
题解
容易看出(dp)式子如下
[dp[i]=min{dp[j]+(sum[i]-sum[j]+i-(j+1)-L)^2} quad (j < i)
]
这个式子为(O(n^2))的复杂度，显然过不去，我们进行一下斜率优化就能优化一维枚举决策点的复杂度，变成(O(n))了。
接下来就需要拆式子，右边有六项，十分的难拆，但我们可以将与(j)有关和与(j)无关的分开，所以我们可以将这个式子进行一个简单的分割。
即让(a[i])为(sum[i]+i-1-L)，(b[j])为(sum[j]+j)。
原式就化为了$$dp[i]=min{dp[j]+(a[i]-b[j])^2} quad (j < i)$$
[dp[i]=min{dp[j]+a[i]^2-2*a[i]*b[j]+b[j]^2}
]
当(j)比(k)更优的时候满足((k<j))
[dp[j]-2*a[i]*b[j]+b[j]^2<dp[k]-2*a[i]*b[k]+b[k]^2
]
[(dp[j]+b[j]^2)-(dp[k]+b[k]^2)<2*a[i]*(b[j]-b[k])
]
$$frac{(dp[j]+b[j]^2)-(dp[k]+b[k]^2)}{(b[j]-b[k])} < 2*a[i]$$
然后(a[i])显然满足单调递增。可以用单调队列去维护。
(q[Head+1])比(q[Head])要优，弹出队首。
然后弹出队尾的时有些麻烦，但结论还是很简单的，如果(k(q[Tail-1],q[Tail]))斜率大于(k(q[Tail],i))就可以弹出队尾。（这个可以简单证明一下）
最后就直接可以每次将队首作为决策转移点去转移了。
代码
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define Fordown(i, r, l) for(register int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}
inline int read() {
int x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
return x * fh;
}
void File() {
#ifdef zjp_shadow
freopen ("P1010.in", "r", stdin);
freopen ("P1010.out", "w", stdout);
#endif
}
typedef long long ll;
const int N = 50100;
int n;
ll sum[N], dp[N], L;
ll a[N], b[N];
#define pow2(x) ((x) * (x))
inline ll Dp(int i, int j) {
return dp[j] + pow2(a[i] - b[j]);
}
inline ll Up(int j, int k) {
return (dp[j] + pow2(b[j]) ) - (dp[k] + pow2(b[k]) );
}
inline ll Down(int j, int k) {
return b[j] - b[k];
}
int q[N];
int Head, Tail = 1;
int main () {
File() ;
n = read();
L = read();
a[0] = - 1 - L;
For (i, 1, n) {
sum[i] = sum[i - 1] + read();
b[i] = sum[i] + i;
a[i] = b[i] - 1 - L;
}
Set(dp, 0x3f); dp[0] = 0;
For (i, 1, n) {
while (Head + 1 < Tail && Up(q[Head + 1], q[Head]) <= 2 * a[i] * Down(q[Head + 1], q[Head]) ) ++ Head;
dp[i] = Dp(i, q[Head]);
while (Head + 1 < Tail && Up(i, q[Tail - 1]) * Down(q[Tail - 1], q[Tail - 2]) <= Up(q[Tail - 1], q[Tail - 2]) * Down(i, q[Tail - 1]) ) -- Tail;
q[Tail ++] = i;
}
printf ("%lld
", dp[n]);
return 0;
}