P 教授有编号为 $1 \sim N$ 的 $N$ 件玩具，第 $i$ 玩具经过压缩后变成一维长度为 $C_i$ 为了方便整理，P 教授要求在一个一维容器中的玩具编号是连续的。如果将第 $i$ 件玩具到第 $j$ 个玩具放到一个容器中，那么容器的长度将为 $$x = j - i + \sum\limits_{k = i} ^ j C_k$$。如果容器长度为 $x$。其制作费用为 $(x - L) ^ 2$。其 $L$ 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 $L$。但他希望费用最小。
链接
BZOJ 1010
题解
令 $f[i]$ 表示前 $i$ 件玩具放进若干个容器中的最小费用，前缀和 $s(n) = \sum\limits_{i = 1} ^ nC[i]$。
转移时枚举前面多少个装在同一个箱子里，设它为 $j$，则第 $j + 1 \sim i$ 个装在同一个箱子里，长度为 $i - j - 1 + s(i) - s(j)$，即
$$f[i] = \min\limits_{j = 0} ^ {i - 1} \big \{ f[j] + (i - j - 1 + s(i) - s(j) - L) ^ 2 \big \}$$
直接计算的复杂度为 $O(n ^ 2)$。
考虑优化，令 $g(i) = s(i) + i - L - 1, h(j) = s(j) + j$，方程变为
$$f[i] = \min\limits_{j = 0} ^ {i - 1} \big \{ f[j] + \big [ g(i) - h(j) \big ] ^ 2 \big \}$$
考虑两个决策 $a, b(a > b)$，若 $a$ 比 $b$ 优，则
$$
\begin{aligned}
f[a] + \big [ g(i) - h(a) \big ] ^ 2 & < f[b] + \big [ g(i) - h(b) \big ] ^ 2 \\
f[a] + g(i) ^ 2 + h(a) ^ 2 - 2g(i)h(a) & < f[b] + g(i) ^ 2 + h(b) ^ 2 - 2g(i)h(b) \\
f[a] + h(a) ^ 2 - 2g(i)h(a) & < f[b] + h(b) ^ 2 - 2g(i)h(b) \\
(f[a] + h(a) ^ 2) - (f[b] + h(b) ^ 2) & < 2g(i)h(a) - 2g(i)h(b) \\
(f[a] + h(a) ^ 2) - (f[b] + h(b) ^ 2) & < 2g(i) \big [h(a) - h(b) \big ] \\
\frac{(f[a] + h(a) ^ 2) - (f[b] + h(b) ^ 2)}{h(a) - h(b)} & < 2g(i) \\
\end{aligned}
$$
代码
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
#include <bits/stdc++.h>
namespace IO {
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
return s == t ? -1 : *s++;
}
template <typename T>
inline void read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return;
c == '-' ? iosig = true : 0;
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
iosig ? x = -x : 0;
}
inline void read(char &c) {
while (c = read(), isspace(c) && c != -1)
;
}
inline int read(char *buf) {
register int s = 0;
register char c;
while (c = read(), isspace(c) && c != -1)
;
if (c == -1) {
*buf = 0;
return -1;
}
do
buf[s++] = c;
while (c = read(), !isspace(c) && c != -1);
buf[s] = 0;
return s;
}
const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
*oh++ = c;
}
template <typename T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
x < 0 ? (print('-'), x = -x) : 0;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void print(const char *s) {
for (; *s; s++) print(*s);
}
inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
struct InputOutputStream {
template <typename T>
inline InputOutputStream &operator>>(T &x) {
read(x);
return *this;
}
template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}
~InputOutputStream() { flush(); }
} io;
}
namespace {
using IO::io;
const int MAXN = 50000;
#define long long long
struct Task {
int n, l, a[MAXN];
long s[MAXN + 1], f[MAXN + 1];
template <typename T>
inline T square(const T &x) {
return x * x;
}
inline long g(const int i) { return s[i] + i - l - 1; }
inline long h(const int j) { return s[j] + j; }
inline double slope(const int a, const int b) {
return double((f[a] + square(h(a))) - (f[b] + square(h(b)))) /
double(h(a) - h(b));
}
inline void solve() {
io >> n >> l;
for (register int i = 0; i < n; i++) io >> a[i];
for (register int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i - 1];
static long q[MAXN];
register long *l = q, *r = q;
for (register int i = 1; i <= n; i++) {
while (l < r && slope(*(l + 1), *l) <= 2 * g(i)) l++;
f[i] = f[*l] + square(g(i) - h(*l));
while (l < r && slope(*r, *(r - 1)) > slope(i, *r)) r--;
*++r = i;
}
io << f[n];
}
} task;
#undef long
}
int main() {
task.solve();
return 0;
}
|
