题目描述
https://www.luogu.com.cn/problem/P3195
简要题意：给定一个长度为 $n$ 的序列 $a$ 和 $L$，现在需要将序列分成若干段，如果将 $a_i$ 到 $a_j$ 放到一段，那么它们的代价是 $(j-i+\sum_{k=i}^ja_k-L)^2$，求最小代价
$n\le 5\times 10^4$
Solution
容易得到 $dp$ 式子，$f_i=min\lbrace f_j+(s_i-s_j+i-j-1-L)^2\rbrace$
我们令 $a_i=s_i+i$，$b_j=s_j+L+1$，那么 $f_i=min\lbrace f_j+(a_i-b_j)^2\rbrace$
化简成直线的形式可以得到 $f_i-a^2_i+2a_ib_j=f_j+b_j^2$，其中 $y=f_j+b^2_j,x=b_j,k=2a_i,b=f_i-a_i^2$
其中 $k$ 和 $x$ 均递增，且 $k>0$，所以可以直接使用单调队列来维护下凸壳
时间复杂度 $O(n)$
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
| #include <iostream>
#define maxn 50010
#define ll long long
using namespace std;
int n, L;
ll a[maxn], b[maxn], f[maxn], s[maxn];
inline double slope(int i, int j) { return 1.0 * (f[i] + b[i] * b[i] - f[j] - b[j] * b[j]) / (b[i] - b[j]); }
int Q[maxn], h, t;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> L;
for (int i = 1, x; i <= n; ++i) cin >> x, s[i] = s[i - 1] + x;
for (int i = 1; i <= n; ++i) a[i] = s[i] + i, b[i] = s[i] + i + L + 1;
Q[h = t = 1] = 0; b[0] = L + 1;
for (int i = 1; i <= n; ++i) {
while (h < t && slope(Q[h], Q[h + 1]) < 2.0 * a[i]) ++h;
f[i] = f[Q[h]] + b[Q[h]] * b[Q[h]] - 2 * a[i] * b[Q[h]] + a[i] * a[i];
while (h < t && slope(Q[t - 1], Q[t]) > slope(Q[t - 1], i)) --t;
Q[++t] = i;
} cout << f[n] << "\n";
return 0;
}
|