「Solution」cdq斜率优化
All in one.
$\mathcal{Template}$
1 |
|
$\mathcal{Building \ Bridges}$
$\mathcal{Link}$
$\mathcal{Sol}$
方程直接一眼: 记 $w_i$ 的前缀和为 $sum_i$ 。
$$
\begin{aligned}
dp_i &= dp_j + (sum_{i-1} - sum_j) + (h_i - h_j) ^ 2 \\
&= dp_j + sum_{i-1} - sum_j + h_i^2 + h_j^2 - 2h_ih_j
\end{aligned}
$$
然后假设 $k_1$ 比 $k_2$ 更优。
那么
$$
\begin{aligned}
dp_{k_1} + sum_{i-1} - sum_{k_1} + h_i^2 + h_{k_1}^2 - 2h_ih_{k_1} &< dp_{k_2} + sum_{i-1} - sum_{k_2} + h_i^2 + h_{k_2}^2 - 2h_ih_{k_2} \\
\rightarrow dp_{k_1} - dp_{k_2} - sum_{k_1} + sum_{k_2} + h_{k_1}^2 - h_{k_2}^2 - 2h_ih_{k_1} + 2h_ih_{k_2} &< 0 \\
dp_{k_1} - dp_{k_2} - sum_{k_1} + sum_{k_2} + h_{k_1}^2 - h_{k_2}^2 &< 2h_ih_{k_1} - 2h_ih_{k_2} \\
\frac{(dp_{k_1} - sum_{k_1} + h_{k_1}^2) - (dp_{k_2} - sum_{k_2} + h_{k_2}^2)}{h_{k_1} - h_{k_2}} &< 2h_i
\end{aligned}
$$
这是个下凸壳。
结果发现 $h_i$ 没有单调性。
带进来就是说 $x$ 和 $k$ 都没有单调性。
所以要用 cdq 来维护。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
using namespace std;
const int MAXN = 1e5 + 5;
const LL INF = 1e18;
int n, que[MAXN];
LL h[MAXN], w[MAXN], sum[MAXN], dp[MAXN];
struct Node { int ind; LL x, y; } a[MAXN], tmp[MAXN];
long double K(int x, int y) {
if (a[x].x == a[y].x) {
if (a[x].y < a[y].y) return INF;
else return -INF;
}
return ((long double)(a[y].y - a[x].y) / (long double)(a[y].x - a[x].x));
}
void cdq(int l, int r) {
if (l == r) {
a[l].y = dp[a[l].ind] - sum[a[l].ind] + h[a[l].ind] * h[a[l].ind];
return;
}
int mid = (l + r) >> 1;
for (int i = l, p = l, q = mid + 1; i <= r; i++) {
if (a[i].ind <= mid) tmp[p++] = a[i];
else tmp[q++] = a[i];
}
for (int i = l; i <= r; i++) a[i] = tmp[i];
cdq(l, mid);
int head = 1, tail = 0;
for (int i = l; i <= mid; i++) {
while (head < tail && K(que[tail - 1], que[tail]) >= K(que[tail - 1], i)) tail--;
que[++tail] = i;
}
for (int i = mid + 1; i <= r; i++) {
// if (a[i].ind == 5) {
// printf("debug\n");
// }
while (head < tail && K(que[head], que[head + 1]) <= 2 * h[a[i].ind]) head++;
int j = que[head];
dp[a[i].ind] = min(dp[a[i].ind], dp[a[j].ind] + (sum[a[i].ind - 1] - sum[a[j].ind]) + (h[a[i].ind] - h[a[j].ind]) * (h[a[i].ind] - h[a[j].ind]));
// printf(" dp[%d] = %d %d\n", a[i].ind, dp[a[i].ind], a[j].ind);
}
cdq(mid + 1, r);
int p = l, q = mid + 1, pos = l;
while (p <= mid && q <= r) {
if (a[p].x < a[q].x) tmp[pos++] = a[p++];
else tmp[pos++] = a[q++];
}
while (p <= mid) tmp[pos++] = a[p++];
while (q <= r) tmp[pos++] = a[q++];
for (int i = l; i <= r; i++) a[i] = tmp[i];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &h[i]);
dp[i] = INF, a[i].x = h[i], a[i].ind = i;
}
dp[1] = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld", &w[i]), sum[i] = sum[i - 1] + w[i];
}
sort(a + 1, a + 1 + n, [](const Node& x, const Node& y) { return x.x < y.x; });
cdq(1, n);
printf("%lld\n", dp[n]);
return 0;
}
$\mathcal{BZOJ4700. 适者}$
$\mathcal{Link}$
$\mathcal{Sol}$
先考虑没有开局双杀这个操作时的答案。
基本的贪心思路，考虑相邻的两个敌人， $(d_1,a_1)$ 和 $(d_2,a_2)$ 。
不交换攻击顺序时造成的代价为 $a_1 \times \frac{d_1}{atk} + a_2 \times \frac{d_2+d_1}{atk}$ 。
如果交换，则代价为 $a_2 \times \frac{d_2}{atk} + a_1 \times \frac{d_2+d_1}{atk}$ 。
如果交换后更优，则有
$$
\begin{aligned}
a_1 \times \frac{d_1}{atk} + a_2 \times \frac{d_2+d_1}{atk} &\le a_2 \times \frac{d_2}{atk} + a_1 \times \frac{d_2+d_1}{atk} \\
a_2 \times \frac{d_1}{atk} &\le a_1 \times \frac{d_2}{atk} \\
\frac{a_2}{d_2} &\le \frac{a_1}{d_1}
\end{aligned}
$$
那么把 $\frac{d}{a}$ 作为关键字排序就可以算出答案。
考虑开局双杀操作，你会发现，直接移除某个人后，其他的人的相对击败顺序并不会变，也就是说，可以直接计算移除某一个人后的贡献。
记前缀血量 $sum_i = \sum_{j = 1}^{i} d_i$ 。
不移除人的答案是 $Ans = \sum_{i = 1}^n \frac{sum_i}{atk}a_i$ 当移除掉第 $j$ 个人后，分前后两部分计算
$$
\begin{aligned}
Ans &= (\sum_{i=1}^{j-1} \frac{sum_i}{atk}a_i) + (\sum_{i=j+1}^{n} \frac{sum_i - d_j}{atk} a_i) \\
&= (\sum_{i=1}^{j-1} \frac{sum_i}{atk}a_i) + (\sum_{i=j+1}^{n} \frac{sum_i}{atk} a_i) - (\sum_{i=j+1}^{n} \frac{d_j}{atk} a_i) \\
&= (\sum_{i = 1}^n \frac{sum_i}{atk}a_i) - \frac{sum_j}{atk}a_j - d_j\sum_{i=j+1}^{n} \frac{a_i}{atk}
\end{aligned}
$$
可以看到改变的值为 $\frac{sum_j}{atk}a_j + d_j\sum_{i=j+1}^{n} \frac{a_i}{atk}$ 。
如果再干掉一个人，假设位置为 $k (k > j)$ 。他会改变 $\frac{sum_k - d_j}{atk}a_k + d_k\sum_{i=k+1}^{n} \frac{a_i}{atk}$ 。
把两次操作合在一起得到
$$
\begin{aligned}
Ans = (\sum_{i = 1}^n \frac{sum_i}{atk}a_i) - (\frac{sum_j}{atk}a_j + d_j\sum_{i=j+1}^{n} \frac{a_i}{atk}) - (\frac{sum_k - d_j}{atk}a_k + d_k\sum_{i=k+1}^{n} \frac{a_i}{atk})
\end{aligned}
$$
然后可以莽一个 $\mathcal{O}(n^2)$ 的暴力 dp 。
可以直接预处理出所有的单杀局面，记为 $dp_{i, 0}$ 。
然后考虑双杀局面 $dp_{i, 1}= \min_{j=1}^{i-1} \{dp_{j, 0} - \frac{sum_i - d_j}{atk}a_i - d_i\sum_{k = i + 1}^n \frac{a_k}{atk}\}$ 。
看起来可以优化。
记 $g_i = \sum_{j = i + 1}^n \frac{a_j}{atk}$ ，假设两个决策点 $k_1$ , $k_2$ , 如果 $k_1$ 优于 $k_2$ 。
$$
\begin{aligned}
dp_{k_1, 0} - \frac{sum_i - d_{k_1}}{atk}a_i - d_i g(i) &\le dp_{k_2, 0} - \frac{sum_i - d_{k_2}}{atk}a_i - d_ig(i) \\
dp_{k_1, 0} - dp_{k_2, 0} &\le \frac{d_{k_2} - d_{k_1}}{atk} a_i \\
\end{aligned}
$$
结果发现 $d_{k_2} - d_{k_1}$ 正负不定，挪不过去。
就强制写一个 cdq 。1
The End「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」