水题笔记_ 学姐的钱包 [翻车, 线段树, DP, DP优化]

LL LL LL

重要的类型说三遍…

善用

1
#define int LL

懵逼的 题目

传送至 vijos

扯淡的 题解

寒假的时候ZYH学长当例题讲的

我们发现, 如果把每一个朋友看成一条线段(左端点是$R_i$, 右端点是$V_i$)的话, 就是一个带权($T_i$)的线段覆盖

设$F_i$为到坐标$i$花的最少时间

显然离散化后我们可以发现一个DP方程
$$
F_i = \min{F_j} + seg_i.cost \,\,(seg_i.le \le j \le seg_i.ri)
$$

Emmmm我们发现满足条件的是一个区间, 求的就是一个区间的最小值, 而这个区间是任意的, 不能用单调队列, 那我们考虑用线段树来维护区间最小值

  • 把所有的线段按照右端点排序 (因为只会在右端点的地方更新答案, 也就是说更新答案和左端点无关)
  • 对于每一条线段, 更新$F$数组
  • $ans = \min{F_i} \,\, (i \in [m, \max V_i])$

然后…我发现…我线段树修改传参数的时候没有吧参数改成LL….

然后dev崩了用的codeblocks, 忘开-Wall…艹又调了半天

沙茶的 代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (4000000 + 5)
#define MAXM (1000000000 + 5)
#define INF (2000000000000000ll)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define LL long long
#define int LL
using namespace std;
struct node
{
LL le, ri, zh;
}a[MAXN], b[MAXN << 3];
int n, m;
LL ans, f[MAXN << 2], sora[MAXN << 2], maxle;
LL min(LL x, LL y)
{
if (x > y) return y;
else return x;
}
void js(int dq, int le, int ri)
{
b[dq].le = le, b[dq].ri = ri;
b[dq].zh = INF;
if (le == ri)
return ;
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
}
LL cx(int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
return b[dq].zh;
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
return cx(RS(dq), le, ri);
else if (ri <= mi)
return cx(LS(dq), le, ri);
else
return min(cx(LS(dq), le, mi), cx(RS(dq), mi + 1, ri));
}
void xg(int dq, int wz, int zh)
{
b[dq].zh = min(b[dq].zh, zh);
if (b[dq].le == b[dq].ri)
return ;
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz <= mi)
xg(LS(dq), wz, zh);
else
xg(RS(dq), wz, zh);
}
bool cmp(node x, node y)
{
if (x.ri != y.ri) return x.ri < y.ri;
else return x.le < y.le;
}
void dp()
{
js(1, 1, maxle);
memset(f, 0x7f, sizeof(f));
f[1] = 0;
xg(1, 1, 0);
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
f[a[i].ri] = min(f[a[i].ri], cx(1, a[i].le, a[i].ri) + a[i].zh);
xg(1, a[i].ri, f[a[i].ri]);
}
ans = INF;
for (int i = m; i <= maxle; i++)
ans = min(ans, f[i]);
}
main()
{
freopen("in.in", "r", stdin);
int t;
scanf("%lld", &t);
for (int tim = 1; tim <= t; tim++)
{
sora[0] = 0;
scanf("%lld%lld", &n, &m);
sora[++sora[0]] = 1, sora[++sora[0]] = m;
for (int i = 1; i <= n; i++)
scanf("%lld%lld%lld", &a[i].ri, &a[i].le, &a[i].zh), sora[++sora[0]] = a[i].le, sora[++sora[0]] = a[i].ri;
sort(sora + 1, sora + sora[0] + 1);
sora[0] = unique(sora + 1, sora + sora[0] + 1) - sora - 1;
maxle = sora[0];
for (int i = 1; i <= n; i++)
a[i].le = lower_bound(sora + 1, sora + sora[0] + 1, a[i].le) - sora,
a[i].ri = lower_bound(sora + 1, sora + sora[0] + 1, a[i].ri) - sora;
m = lower_bound(sora + 1, sora + sora[0] + 1, m) - sora;
dp();
if (ans >= INF)
printf("Case #%d: -1\n", tim);
else
printf("Case #%d: %lld\n", tim, ans);
}
return 0;
}

/*
3
5 9
5 1 1
10 4 10
8 1 10
11 6 1
7 3 8
4 5
2 1 1
3 2 1
4 3 1
8 4 1
3 10
5 1 3
8 2 5
10 9 2


1
1 22
22 1 1
*/

By sb Cansult