abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S3947 【收历史作业】

发表于 更新于

Description

给你一个 $n \times m$ 的地图，有 $k$ 个格子里有数，现在有一人从左上角出发，要走到右下角。现在请你求出在走的路程最短的情况下所经过的数的权值和最大是多少。

Solution

因为要求走的路程最短，所以只能够向下或向右走。

所以对于两个坐标 $(a, b)$ 和 $(c, d)$ ，能够从 $(a, b)$ 走到 $(c, d)$ 的条件是 $c \geq a$ 且 $d \geq b$ 。

考虑用 DP 来做，设 $f_{i, j}$ 表示当前做到位置 $(i, j)$ 时的最优解，这样我们就可以保证上文所说的 $c \geq a$ 的这个条件了，发现对于 $d \geq b$ 这个条件我们可以用 线段树 来维护，然后就可以进行转移了。

但是我们可以发现 $n$ 和 $m$ 都很大，所以我们要 离散化 ，这样状态就转为了设 $f[i]$ 表示前 $i$ 个位置的最优解。

注意，我们要在离散化后对有数的位置排序，排序时以横坐标为第一关键字，纵坐标为第二关键字，从小到大排序。

然后就可以在 $O(k \log k)$ 的时间内完成了。

记得要开 long long 。

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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include <cstdio>
#define maxK 100010
long long lend = 0, lend2 = 0, len = 0, n = 0, m = 0, k = 0;
struct nodea{ long long l, r, lc, rc, c; } a[maxK << 2];
struct nodeb{ long long x, y, c; } b[maxK];
long long f[maxK], d[maxK << 1], d2[maxK << 1];
long long calc (long long p)
{
	return (b[p].x - 1) * lend2 + b[p].y;
}
long long max (long long x, long long y)
{
	return x > y ? x : y;
}
void px (long long l, long long r)
{
	long long x = l, y = r, mid = calc((l + r) / 2);
	while(x <= y)
	{
		while(calc(x) < mid)
		{
			x++;
		}
		while(calc(y) > mid)
		{
			y--;
		}
		if(x <= y)
		{
			nodeb t = b[x];
			b[x] = b[y];
			b[y] = t;
			x++;
			y--;
		}
	}
	if(l < y)
	{
		px(l, y);
	}
	if(x < r)
	{
		px(x, r);
	}
}
void px2 (long long l, long long r)
{
	long long x = l, y = r, mid = d[(l + r) / 2];
	while(x <= y)
	{
		while(d[x] < mid)
		{
			x++;
		}
		while(d[y] > mid)
		{
			y--;
		}
		if(x <= y)
		{
			long long t = d[x];
			d[x] = d[y];
			d[y] = t;
			x++;
			y--;
		}
	}
	if(l < y)
	{
		px2(l, y);
	}
	if(x < r)
	{
		px2(x, r);
	}
}
void build (long long l, long long r)
{
	len++;
	a[len].l = l;
	a[len].r = r;
	a[len].lc = -1;
	a[len].rc = -1;
	a[len].c = 0;
	long long now = len;
	if(l < r)
	{
		long long mid = (l + r) / 2;
		a[len].lc = len + 1;
		build(l, mid);
		a[now].rc = len + 1;
		build(mid + 1, r);
	}
}
void change (long long now, long long x, long long t)
{
	if(a[now].l == a[now].r)
	{
		a[now].c = t;
		return ;
	}
	long long mid = (a[now].l + a[now].r) / 2;
	if(x <= mid)
	{
		change(a[now].lc, x, t);
	}
	else
	{
		change(a[now].rc, x, t);
	}
	a[now].c = max(a[a[now].lc].c, a[a[now].rc].c);
}
long long query (long long now, long long l, long long r)
{
	if(a[now].l == l && a[now].r == r)
	{
		return a[now].c;
	}
	long long mid = (a[now].l + a[now].r) / 2;
	if(r <= mid)
	{
		return query(a[now].lc, l, r);
	}
	else if(mid + 1 <= l)
	{
		return query(a[now].rc, l, r);
	}
	else
	{
		return max(query(a[now].lc, l, mid), query(a[now].rc, mid + 1, r));
	}
}
long long find (long long x)
{
	long long l = 1, r = lend2;
	while(l < r)
	{
		long long mid = (l + r) / 2;
		if(d2[mid] < x)
		{
			l = mid + 1;
		}
		else
		{
			r = mid;
		}
	}
	return l;
}
int main ()
{
	scanf("%lld %lld %lld", &n, &m, &k);
	for(long long i = 1;i <= k; i++)
	{
		scanf("%lld %lld %lld", &b[i].x, &b[i].y, &b[i].c);
		b[i].x++;
		d[++lend] = b[i].y;
	}
	d[++lend] = m;
	px2(1, lend);
	d2[++lend2] = d[1];
	for(long long i = 2;i <= lend; i++)
	{
		if(d[i] != d[i - 1])
		{
			d2[++lend2] = d[i];
		}
	}
	for(long long i = 1;i <= k; i++)
	{
		b[i].y = find(b[i].y);
	}
	px(1, k);
	if(calc(k) != (n - 1) * lend + find(m))
	{
		k++;
		b[k].x = n;
		b[k].y = find(m);
		b[k].c = 0;
	}
	build(1, lend2);
	for(long long i = 1;i <= k; i++)
	{
		f[i] = query(1, 1, b[i].y) + b[i].c;
		change(1, b[i].y, max(f[i], query(1, b[i].y, b[i].y)));
	}
	printf("%lld", f[k]);
	return 0;
}