Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

P4655 [CEOI2017]Building Bridges

发表于 分类于
本文字数： 2.8k 阅读时长 ≈ 3 分钟
标签：        

P4655 [CEOI2017]Building Bridges

在一般的斜率优化问题中，因为 $x$ 是单调的，所以可以用单调队列维护凸包；因为 $k$ 是单调的，所以可以用单调队列求答案。如果不满足前者，需要用 cdq分治 ；如果不满足后者，需要二分斜率。

对于当前分治的区间 $[l, r]$ ，考虑从 $[l, mid]$ 转移对 $[mid + 1, r]$ 答案的影响。我们需要左侧 $x$ 是单调的，那么可以单调队列维护凸包；我们需要右侧 $k$ 是单调的，那么可以用单调队列得到答案。所以每次将左侧按照 $x$ 排序，右侧按照 $k$ 排序，做完后将右侧还原。

这种写法在 CDQ 内部要排序，复杂度 $O(n \log ^ 2n)$ ；一种写法是先将整个序列排序，再分出来，CDQ 内部可以归并排序，复杂度 $O(n \log 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
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
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
template <class Type>
void chkmin(Type &x, Type k)
{
    k < x && (x = k);
}
const int N = 1e5 + 10;
const LL inf = 1e18;
int n, p[N];
int hd, tl, q[N];
LL f[N], h[N], s[N];
LL Y(int x)
{
    return h[x] * h[x] + f[x] - s[x];
}
double slp(int x, int y)
{
    if (h[x] == h[y])
        return Y(x) < Y(y) ? inf : -inf;
    return (double)(Y(x) - Y(y)) / (h[x] - h[y]);
}
void cdq(int l, int r)
{
    if (l == r)
        return;
    int mid = l + r >> 1;
    cdq(l, mid);
    sort(p + l, p + mid + 1, [&](int x, int y)
         { return h[x] < h[y]; });
    sort(p + mid + 1, p + r + 1, [&](int x, int y)
         { return h[x] < h[y]; });
    hd = 1, tl = 0;
    for (int i = l; i <= mid; i++)
    {
        while (hd < tl && slp(q[tl - 1], q[tl]) > slp(q[tl], p[i]))
            tl--;
        q[++tl] = p[i];
    }
    for (int i = mid + 1; i <= r; i++)
    {
        while (hd < tl && slp(q[hd], q[hd + 1]) < h[p[i]] * 2)
            hd++;
        chkmin(f[p[i]], f[q[hd]] + (h[q[hd]] - h[p[i]]) * (h[q[hd]] - h[p[i]]) + s[p[i] - 1] - s[q[hd]]);
    }
    sort(p + mid + 1, p + r + 1, [&](int x, int y)
         { return x < y; });
    cdq(mid + 1, r);
}
int main()
{
    read(n);
    for (int i = 1; i <= n; i++)
        read(h[i]);
    for (int i = 1; i <= n; i++)
        read(s[i]), s[i] += s[i - 1];
    for (int i = 2; i <= n; i++)
        f[i] = inf;
    for (int i = 1; i <= n; i++)
        p[i] = i;
    cdq(1, n);
    write(f[n]);
    return 0;
}
相关文章