传送~

Description

共有$n$个玩具,每个玩具长度$c_i$, 将$i$至$j$连续的玩具放入一个容器$i<j$,其长度$x=j-i+\sum_{k=i}^j{c_k}$.制作一个容器的费用为$(x-L)^2$,其中L为常数.求将所有玩具都放入容器中的费用最小值.

$n\leq 5*10^4, 1\leq L,c_i\leq 10^7$

Solution

$O(n^2)$

考虑dp.

设$f_i$为1至$i$的所有玩具都放入容器中的最小费用.显然可以得到如下转移方程

设$sum_i$为$\sum_{j=1}^i{c_j}$,则原方程可化为

这样我们可以做到$O(n^2)$.但对于$5*10^4$,这是远远不够的.

$O(n)$

这个式子实在是太丑了…于是,根据式子中各成分与$i,j$的关系,我们可以设$a_i=sum_i+i,b_i=sum_i+i+L$,则原方程又双叒叕可以表示为

式子瞬间简洁多了.

这时我们可以考虑斜率优化.由斜率优化套路,即比较两种转移策略,我们设$j>k$且从从$j$转移优于$k$,则必须满足

这时我们发现左边与当前$i$无关(这是可以用斜率优化的必要条件)且很像一次函数的点斜式.我们设$slope(j,k)$为上面的左式,即斜率.则当$j>k$且$slope(j,k)<2*a_i$时,$j$比$k$优.由于$a_i$单调递增,我们可以用单调队列维护斜率,使$slope(i+1, i)$单调递增,且队首最优.

Code

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
#include <bits/stdc++.h>
#define A(i) ((i)+sum[i])
#define B(i) ((i)+L+1+sum[i])
#define S(i) 1ll*(i)*(i)
using namespace std;
template<typename T> inline void read(T& x) {
char ch = getchar(); T a = 0, b = 1;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') b = -1, ch = getchar();
while (ch >= '0' && ch <= '9') a = (a<<1)+(a<<3)+(ch^48), ch = getchar();
x = a*b;
}
typedef long long ll;
const int maxn = 5e4;
int n, sum[maxn+10], L, q[maxn+10];
ll f[maxn+10];
inline double slope(int j, int k) {
return 1.0*(f[j]+S(B(j))-f[k]-S(B(k)))/(B(j)-B(k));
}
int main() {
read(n); read(L);
for (int i = 1; i <= n; ++i) {
read(sum[i]); sum[i] += sum[i-1];
}
int l = 0, r = 0;
for (int i = 1; i <= n; ++i) {
while (l < r && slope(q[l+1], q[l]) <= 2*A(i)) ++l; //此时q[l]比q[l+1]更劣,由于a[i]递增,故之后一直更劣,弹出
f[i] = f[q[l]]+S(A(i)-B(q[l]));
while (l < r && slope(q[r], q[r-1]) > slope(i, q[r])) --r; //保持队列中斜率单调递增
q[++r] = i;
}
printf("%lld", f[n]); //一定记得开longlong
return 0;
}

THANK YOU FOR READING THIS!