[Codeforces 988.F] Rain and Umbrellas（序列dp）

发表于 分类于 ，
Codeforces 988.F

F. Rain and Umbrellas

time limit per test:2 seconds
memory limit per test:256 megabytes
input:standard input
output:standard output

Polycarp lives on a coordinate line at the point $x=0$. He goes to his friend that lives at the point $x=a$. Polycarp can move only from left to right, he can pass one unit of length each second.

Now it’s raining, so some segments of his way are in the rain. Formally, it’s raining on $n$ non-intersecting segments, the $i$-th segment which is in the rain is represented as $[l_i,r_i]$ ($0≤l_i<r_i≤a$).

There are $m$ umbrellas lying on the line, the $i$-th umbrella is located at point $x_i$ ($0≤x_i≤a$) and has weight $p_i$. When Polycarp begins his journey, he doesn’t have any umbrellas.

During his journey from $x=0$ to $x=a$ Polycarp can pick up and throw away umbrellas. Polycarp picks up and throws down any umbrella instantly. He can carry any number of umbrellas at any moment of time. Because Polycarp doesn’t want to get wet, he must carry at least one umbrella while he moves from $x$ to $x+1$ if a segment $[x,x+1]$ is in the rain (i.e. if there exists some $i$ such that $l_i≤x$ and $x+1≤r_i$).

The condition above is the only requirement. For example, it is possible to go without any umbrellas to a point where some rain segment starts, pick up an umbrella at this point and move along with an umbrella. Polycarp can swap umbrellas while he is in the rain.

Each unit of length passed increases Polycarp’s fatigue by the sum of the weights of umbrellas he carries while moving.

Can Polycarp make his way from point $x=0$ to point $x=a$? If yes, find the minimum total fatigue after reaching $x=a$, if Polycarp picks up and throws away umbrellas optimally.

Input

The first line contains three integers $a$, $n$ and $m$ ($1≤a,m≤2000,1≤n≤⌈\frac{a}{2}⌉$) — the point at which Polycarp’s friend lives, the number of the segments in the rain and the number of umbrellas.

Each of the next $n$ lines contains two integers $l_i$ and $r_i$ ($0≤l_i<r_i≤a$) — the borders of the $i$-th segment under rain. It is guaranteed that there is no pair of intersecting segments. In other words, for each pair of segments $i$ and $j$ either $r_i<l_j$ or $r_j<l_i$.

Each of the next $m$ lines contains two integers $x_i$ and $p_i$ ($0≤x_i≤a$, $1≤p_i≤10^5$) — the location and the weight of the $i$-th umbrella.

Output

Print “-1“ (without quotes) if Polycarp can’t make his way from point $x=0$ to point $x=a$. Otherwise print one integer — the minimum total fatigue after reaching $x=a$, if Polycarp picks up and throws away umbrellas optimally.

Examples

input output
10 2 4
3 7
8 10
0 10
3 4
8 1
1 2		 14
10 1 1
0 9
0 5		 45
10 1 1
0 9
1 5		 -1

Note

In the first example the only possible strategy is to take the fourth umbrella at the point $x=1$, keep it till the point $x=7$ (the total fatigue at $x=7$ will be equal to $12$), throw it away, move on from $x=7$ to $x=8$ without an umbrella, take the third umbrella at x=8 and keep it till the end (the total fatigue at $x=10$ will be equal to $14$).

In the second example the only possible strategy is to take the first umbrella, move with it till the point $x=9$, throw it away and proceed without an umbrella till the end.

解题思路

这肯定是一道 dp 题。
注意题目是从 $0$ 位置开始的，下列解法均先把所有位置右移了1格

首先有一个很显然的贪心：不可能同时拿着多把伞。
然后预处理一下哪些地方下雨，哪些地方有伞，每把伞在什么位置 $O(n\cdot a+m)$

下面是 dp：
考虑到不同的状态取决于当前所在位置和当前拿着的伞，令 $dp[i][j]$ 表示走到 $i$ 时拿着第 $j$ 把伞（$j=0$ 表示没拿伞），分情况转移（已知 $dp[i][j]$，刷表法）：

  • 拿着第 $j$ 把伞走到 $i+1$：$dp[i+1][j] = min(dp[i+1][j],dp[i][j] + weight[j])$
    前提： $j \neq 0$
  • 放下第 $j$ 把伞走到 $i+1$：$dp[i+1][0] = min(dp[i+1][0], dp[i][j])$
    前提：$i$ 处不下雨
  • 拿起 $i$ 处的最轻的伞（假设是第 $k$ 把伞）走到 $i+1$：$dp[i+1][k] = min(dp[i+1][k], dp[i][j] + w[k]$
    前提：$i$ 处有伞

边界条件为 $dp[0][0] = 0$
答案就是 $\min\limits_{i=0}^m dp[a][i]$

坑点：同一个位置可以有多把伞！

时间复杂度 $O(n\cdot a)$

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
# include<cstdio>
# include<cstring>
# include<algorithm>

using namespace std;

const int N = 2005;
bool rain[N];
struct Umbrella{
	int pos, w;
}umb[N];
int a, n, m, x, y, umbre[N];
int dp[N][N], ans = 1e9;

int main(){
	scanf("%d%d%d", &a, &n, &m);
	a++;
	for(int i = 1; i <= n; i++){
		scanf("%d%d", &x, &y);
		x++, y++;
		for(int j = x; j < y; j++)
			rain[j] = 1;
	}
	for(int i = 1; i <= m; i++){
		scanf("%d%d", &x, &y);
		x++;
		umb[i].pos = x;
		umb[i].w = y;
		if(!umbre[x] || (umbre[x] && y < umb[umbre[x]].w))
			umbre[x] = i;
	}
	memset(dp, 0x3f, sizeof dp);
	dp[0][0] = 0;
	for(int i = 0; i < a; i++){
		for(int j = 0; j <= m; j++){
			if(umb[j].pos > i)	continue;
			if(j)
				dp[i+1][j] = min(dp[i+1][j], dp[i][j] + umb[j].w);
			if(!rain[i])
				dp[i+1][0] = min(dp[i+1][0], dp[i][j]);
			if(umbre[i])
				dp[i+1][umbre[i]] = min(dp[i+1][umbre[i]], dp[i][j] + umb[umbre[i]].w);
		}
	}
	for(int i = 0; i <= m; i++)
		ans = min(ans, dp[a][i]);
	if(ans == 1e9)	puts("-1");
	else	printf("%d\n", ans);
	return 0;
}