A12282. Lunar New Year and Red Envelopes
编程题
普及/提高-
知识点
题目描述
Lunar New Year is approaching, and Bob is going to receive some red envelopes with countless money! But collecting money from red envelopes is a time-consuming process itself.
Let's describe this problem in a mathematical way. Consider a timeline from time $1$ to $n$ . The $i$ -th red envelope will be available from time $s_i$ to $t_i$ , inclusive, and contain $w_i$ coins. If Bob chooses to collect the coins in the $i$ -th red envelope, he can do it only in an integer point of time between $s_i$ and $t_i$ , inclusive, and he can't collect any more envelopes until time $d_i$ (inclusive) after that. Here $s_i \leq t_i \leq d_i$ holds.
Bob is a greedy man, he collects coins greedily — whenever he can collect coins at some integer time $x$ , he collects the available red envelope with the maximum number of coins. If there are multiple envelopes with the same maximum number of coins, Bob would choose the one whose parameter $d$ is the largest. If there are still multiple choices, Bob will choose one from them randomly.
However, Alice — his daughter — doesn't want her father to get too many coins. She could disturb Bob at no more than $m$ integer time moments. If Alice decides to disturb Bob at time $x$ , he could not do anything at time $x$ and resumes his usual strategy at the time $x + 1$ (inclusive), which may lead to missing some red envelopes.
Calculate the minimum number of coins Bob would get if Alice disturbs him optimally.
Let's describe this problem in a mathematical way. Consider a timeline from time $1$ to $n$ . The $i$ -th red envelope will be available from time $s_i$ to $t_i$ , inclusive, and contain $w_i$ coins. If Bob chooses to collect the coins in the $i$ -th red envelope, he can do it only in an integer point of time between $s_i$ and $t_i$ , inclusive, and he can't collect any more envelopes until time $d_i$ (inclusive) after that. Here $s_i \leq t_i \leq d_i$ holds.
Bob is a greedy man, he collects coins greedily — whenever he can collect coins at some integer time $x$ , he collects the available red envelope with the maximum number of coins. If there are multiple envelopes with the same maximum number of coins, Bob would choose the one whose parameter $d$ is the largest. If there are still multiple choices, Bob will choose one from them randomly.
However, Alice — his daughter — doesn't want her father to get too many coins. She could disturb Bob at no more than $m$ integer time moments. If Alice decides to disturb Bob at time $x$ , he could not do anything at time $x$ and resumes his usual strategy at the time $x + 1$ (inclusive), which may lead to missing some red envelopes.
Calculate the minimum number of coins Bob would get if Alice disturbs him optimally.
输入格式
The first line contains three non-negative integers $n$ , $m$ and $k$ ( $1 \leq n \leq 10^5$ , $0 \leq m \leq 200$ , $1 \leq k \leq 10^5$ ), denoting the length of the timeline, the number of times Alice can disturb Bob and the total number of red envelopes, respectively.
The following $k$ lines describe those $k$ red envelopes. The $i$ -th line contains four positive integers $s_i$ , $t_i$ , $d_i$ and $w_i$ ( $1 \leq s_i \leq t_i \leq d_i \leq n$ , $1 \leq w_i \leq 10^9$ ) — the time segment when the $i$ -th envelope is available, the time moment Bob can continue collecting after collecting the $i$ -th envelope, and the number of coins in this envelope, respectively.
The following $k$ lines describe those $k$ red envelopes. The $i$ -th line contains four positive integers $s_i$ , $t_i$ , $d_i$ and $w_i$ ( $1 \leq s_i \leq t_i \leq d_i \leq n$ , $1 \leq w_i \leq 10^9$ ) — the time segment when the $i$ -th envelope is available, the time moment Bob can continue collecting after collecting the $i$ -th envelope, and the number of coins in this envelope, respectively.
输出格式
Output one integer — the minimum number of coins Bob would get if Alice disturbs him optimally.
输入输出样例
输入 #1
5 0 2 1 3 4 5 2 5 5 8
输出 #1
13
输入 #2
10 1 6 1 1 2 4 2 2 6 2 3 3 3 3 4 4 4 5 5 5 5 7 6 6 6 9
输出 #2
2
输入 #3
12 2 6 1 5 5 4 4 6 6 2 3 8 8 3 2 9 9 5 6 10 10 7 8 12 12 9
输出 #3
11
说明/提示
In the first sample, Alice has no chance to disturb Bob. Therefore Bob will collect the coins in the red envelopes at time $1$ and $5$ , collecting $13$ coins in total.
In the second sample, Alice should disturb Bob at time $1$ . Therefore Bob skips the first envelope, collects the second one and can not do anything after that. So the answer is $2$ .
In the second sample, Alice should disturb Bob at time $1$ . Therefore Bob skips the first envelope, collects the second one and can not do anything after that. So the answer is $2$ .