Skip to content

1271: 治疗项目

题目

题目描述

村庄有 $N$ 个房屋,编号为 $1$ 到 $N$,每个房屋住有一个村民,第 $i$ 个房屋居住编号为村民 $i$。

现在,这 $N$ 个房屋里的村民全部感染 COVILLAGE-19 病毒,有 $M$ 个治疗方案被提出,第 $i$ 个治疗方案描述为,在第 $T_i$ 天的晚上,编号在 $[L_i,R_i]$ 区间内的村民被治愈。

COVILLAGE-19 病毒还会继续传播,在某天早上,如果村民 $i$ 被感染,那么村民 $i+1$ 和村民 $i-1$ 也会被感染,因为病毒威力巨大,所以被治愈的村民有可能再次被感染。

您是村长,您要选择一些方案使得村庄所有村民全部被治愈,一天可以进行很多方案。

第 $i$ 个方案要花费 $C_i$,求最小花费。

输入格式

第一行两个整数 $N,M$ 代表村民数和方案数。 接下来 $M$ 行每行四个整数 $T_i,L_i,R_i,C_i$ 代表一个治疗方案。

输出格式

一行一个整数代表最小花费。 如果无法全部治愈,输出 $-1$。

样例输入

样例输入 1

text 10 5 2 5 10 3 1 1 6 5 5 2 8 3 7 6 10 4 4 1 3 1

样例输入 2

text 10 5 2 6 10 3 1 1 5 5 5 2 7 3 8 6 10 4 4 1 3 1

样例输入 3

text 10 5 1 5 10 4 1 1 6 5 1 4 8 3 1 6 10 3 1 1 3 1

样例输出

样例输出 1

text 7

执行过程如下(红色为被病毒感染,绿色为治愈):

在第二天晚上,执行第 $1$ 个方案,情况如下: $\color{Red}1\ 2\ 3\ 4\color{Green}\ 5\ 6\ 7\ 8\ 9\ 10$

在第三天早上,村民 $5$ 被感染,情况如下: $\color{Red}1\ 2\ 3\ 4\ 5\color{Green}\ 6\ 7\ 8\ 9\ 10$

在第四天早上,村民 $6$ 被感染,情况如下: $\color{Red}1\ 2\ 3\ 4\ 5\ 6\color{Green}\ 7\ 8\ 9\ 10$

在第四天晚上,执行第 $5$ 个方案,情况如下: $\color{Green}1\ 2\ 3\color{Red}\ 4\ 5\ 6\color{Green}\ 7\ 8\ 9\ 10$

在第五天早上,村民 $3,7$ 被感染,情况如下: $\color{Green}1\ 2\color{Red}\ 3\ 4\ 5\ 6\ 7\color{Green}\ 8\ 9\ 10$

在第五天晚上,执行第 $3$ 个方案,情况如下: $\color{Green}1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10$

全部治愈,这三个方案花费为 $7$,为最小花费。

样例输出 2

text -1

样例输出 3

text 7

数据范围

时间限制:5000 ms 空间限制:512 mb

全局限制

  • $1\leq N, T_i, C_i\leq 10^9$
  • $1\leq M\leq 10^5$
  • $1\leq L_i\leq R_i\leq N$

部分限制

  • $(\text{15 points})~ T_i = 1$
  • $(\text{25 points})~ M\leq 16$
  • $(\text{30 points})~ M\leq 5000$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!