首页 题解

# Description

Luogu传送门

# Solution

斜率优化dp

非常好的一道斜率优化，完全理解题目都用了好长时间 QwQ

其实如果你已经完全理解了这道题也不是特别难了。

我们可以选两个下标，然后把经过这两个下标的线全部删掉。

不难发现，交叉的线是没有用的，所以对于上方的一个点，我们只保留它与下方连边中最右边的点即可。

然后这张图就变成了好多不相交的线，这样就可以列出朴素 dp\text{dp} 了。

设 fif_i 表示把前 ii 条弦全部切掉的最小花费，那么有转移方程：

fi=min⁡(fj+minlu[j+1]−1×minrv[i]+1)f_i = \min(f_j + minl_{u[j + 1] - 1} \times minr_{v[i] + 1})

minl,minrminl, minr 分别是 aa 的前缀最小值，和 bb 的后缀最小值。

然后这就已经是一个斜率优化可以做的式子了。

注意：标准的斜率优化式子为 b=y−kxb = y - kx，而这里是加法，所以求斜率时要取反。

# Code

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
#include <bits/stdc++.h>
#define int long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 3e5 + 10;
const int INF = 2e18;
int n, m;
struct node{
    int l, r;
    inline bool operator < (const node &b) const{
        return l != b.l ? l < b.l : r > b.r;
    }
}p[N];
int a[N], b[N], ml[N], mr[N];
int u[N], v[N], tot;
int f[N], q[N];

inline double X(int i) {return 1.0 * ml[u[i + 1] - 1];}
inline double Y(int i) {return 1.0 * f[i];}
inline double K(int i) {return 1.0 * mr[v[i] + 1];}
inline double slope(int i, int j) {return (X(i) == X(j)) ?  INF :  1.0 * (Y(i) - Y(j)) / (X(j) - X(i));}

signed main(){
    // freopen("P6047.in", "r", stdin);
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i <= n; ++i) b[i] = read();
    for(int i = 1; i <= m; ++i) p[i] = (node){read(), read()};
    sort(p + 1, p + 1 + m);
    int mx = 0;
    for(int i = 1; i <= m; ++i){
        if(p[i].r > mx) u[++tot] = p[i].l, v[tot] = p[i].r;
        mx = max(mx, p[i].r);
    }
    m = tot;
    ml[0] = mr[n + 1] = INF;
    for(int i = 1; i <= n; ++i) ml[i] = min(ml[i - 1], a[i]);
    for(int i = n; i >= 0; --i) mr[i] = min(mr[i + 1], b[i]);
    int head = 1, tail = 1;
    for(int i = 1; i <= m; ++i){
        while(head < tail && slope(q[head], q[head + 1]) < K(i)) head++;
        int j = q[head];
        f[i] = f[j] + K(i) * X(j);
        while(head < tail && slope(q[tail], q[tail - 1]) > slope(q[tail], i)) tail--;
        q[++tail] = i;
    }
    write(f[m]), puts("");
    return 0;
}
// X.K.

阅读次数 次