bzoj1010-玩具装箱

题意

n个玩具,每个玩具长度为$c[i]$,制造一个长度为x的容器需要$(x - L) ^ 2$元,可以将下标连续的玩具
放在同一个容器中,两两玩具之间需要加一个长度为1的垫子(容器的头和尾不用)。 问将所有玩具装到容器中的最小价值。

$1 \leq n \leq 50000, 1 \leq L,c[i] \leq 10000000$

分析

$dp[i]$ 表示装前i个玩具需要的最小代价
$$dp[i] = Min(dp[j] + (pre[i] - pre[j] + i - j - 1 - L) ^ 2), j \in [1,i-1]$$

其中$pre[i]$为长度的前缀和。

设$a[i] = pre[i] + i, b = 1 + L$

$M[i][j] = dp[j] + (pre[i] - pre[j] + i - j - 1 - L) ^ 2$

对于两个决策j和k(j < k),若k决策优于j决策,则有$M[i][j] > M[i][k]$

我们来继续化简一下这个式子。

可以得到
$$\frac{(dp[j] + a[j]^2) - (dp[k] + a[k])^2}{a[j] - a[k]} < 2a[i] - 2b$$

设$C[i] = 2a[i] - 2b$,把不等式左边看成一个斜率$slope(j,k)$

所以我们只要维护一个$slope$单调递增的队列,为什么呢?

如果$slope(q[i-1],q[i]) > slope(q[i],q[i+1])$ ,那么当q[i]比q[i-1]优的时候,q[i+1]一定比q[i]优,所以q[i]就没有存在的必要了。 所以我们需要维护的是一个递增的队列。

假设队列中的i位置的值是决策点, 那么有
$$\begin{cases}
slope(q[i-1],q[i]) < C[i]\\
slope(q[i],q[i+1]) >= C[i]
\end{cases}$$

一般情况下只要二分这个i值就可以了,但是本题中$C[i]$是单调不降的,所以对于决策j,k(j < k), k优于j决策的话,那么对于$i \in [k+1,n]$都适用,因此j决策就没有存在的必要了,因此我们可以用单调队列进行优化

代码

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
43
44
45
46
47
48
49
50
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 5e4 + 5;
ll pre[maxn], a[maxn], c[maxn], dp[maxn];

inline double slope(int i, int k) {
return 1.0 * ((dp[i] + a[i] * a[i]) - (dp[k] + a[k] * a[k])) /
(a[i] - a[k]);
}
int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
int n, L;
scanf("%d%d", &n, &L);
for (int i = 1; i <= n; i++)
scanf("%lld", &c[i]), pre[i] = pre[i - 1] + c[i], a[i] = pre[i] + i;
int b = 1 + L;
int l = 1, r = 1;
vector<int> dq(n + 2);
dq[1] = 0;
for (int i = 1; i <= n; i++) {
while (l < r && slope(dq[l], dq[l + 1]) < 2 * a[i] - 2 * b) l++;
int k = dq[l];
dp[i] = dp[k] + (a[i] - a[k] - b) * (a[i] - a[k] - b);
while (l < r && slope(dq[r], i) < slope(dq[r - 1], dq[r])) r--;
dq[++r] = i;
}
printf("%lld\n", dp[n]);
}
Thank you for your support!