LOJ3282

Solution

先忽略治疗方案的出现时间,考虑从左往右进行DP,设f(i)f(i)表示考虑到第ii个方案,且已经可以治愈1Ri1 \sim R_i的所有病人的最小代价

方案ii可以向方案jj转移当且仅当RiLj+1TiTjR_i - L_j + 1 \ge |T_i - T_j|,把绝对值拆开后就是LjTj/Lj+TjL_j - T_j / L_j + T_j要满足在某个范围内

发现这实际上就是一个最短路问题,用线段树套set(一维是TT,一维是LjTj/Lj+TjL_j - T_j / L_j + T_j)优化上述建边过程后跑Dijkstra即可

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
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;
typedef pair <long long, int> pli;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 1e5;

int N, M;
struct item
{
int t, l, r, c;

inline void input () { t = read<int>(), l = read<int>(), r = read<int>(), c = read<int>(); }

inline bool operator < (const item &rhs) const & { return t < rhs.t; }

} A[MAXN + 5];

priority_queue <pli, vector <pli>, greater <pli> > Q;

LL Dis[MAXN + 5];

struct SEG
{
#define mid ((l + r) >> 1)
#define ls o << 1
#define rs o << 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r
set <pii> node[MAXN * 4 + 5];

inline void insert (int o, int l, int r, int x, pii val)
{
node[o].insert (val);
if (l == r) return ;
if (x <= mid) insert (lson, x, val);
else insert (rson, x, val);
}

inline void update (int o, int l, int r, int x, int y, int lim, LL d)
{
if (x > y) return ;

if (x <= l && r <= y)
{
while (node[o].size() && node[o].begin() -> x <= lim)
{
int p = node[o].begin() -> y;

if (Chkmin (Dis[p], d + A[p].c)) Q.push (mp (Dis[p], p));

node[o].erase (node[o].begin());
}

return ;
}

if (x <= mid) update (lson, x, y, lim, d);
if (y > mid) update (rson, x, y, lim, d);
}

#undef mid
} T[2];

inline void Solve ()
{
sort (A + 1, A + M + 1);

for (int i = 1; i <= M; ++i)
{
T[0].insert (1, 1, M, i, mp (A[i].l - A[i].t, i));
T[1].insert (1, 1, M, i, mp (A[i].l + A[i].t, i));
}

memset (Dis, 0x3f, sizeof Dis);

for (int i = 1; i <= M; ++i) if (A[i].l == 1)
{
Dis[i] = A[i].c;
Q.push (mp (Dis[i], i));
}

static int Vis[MAXN + 5];

while (!Q.empty())
{
int x = Q.top().y; Q.pop();
if (Vis[x]) continue;
Vis[x] = 1;

T[0].update (1, 1, M, 1, x - 1, A[x].r - A[x].t + 1, Dis[x]);
T[1].update (1, 1, M, x + 1, M, A[x].r + A[x].t + 1, Dis[x]);
}

LL ans = 2e18;
for (int i = 1; i <= M; ++i) if (A[i].r == N) Chkmin (ans, Dis[i]);

if (ans >= 2e18) puts("-1");
else cout << ans << endl;
}

inline void Input ()
{
N = read<int>(), M = read<int>();
for (int i = 1; i <= M; ++i) A[i].input ();
}

int main ()
{

#ifdef hk_cnyali
freopen("treatment.in", "r", stdin);
freopen("treatment.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}