Air Cownditioning II

题目描述

在 Farmer John 的农场经历了有记录以来最炎热的夏天，他需要一种方法让奶牛降温。因此，他决定投资一些空调。 Farmer John 有 $N$ 头奶牛（$1 \leq N \leq 20$），它们住在一座牛棚里。牛棚包含一排连续的牛栏，编号为 $1 \ldots 100$。第 $i$ 头奶牛占据一段牛栏区间，从牛栏 $s_i$ 开始到牛栏 $t_i$ 结束。不同奶牛所占据的牛栏区间两两互不重叠。 奶牛有不同的降温需求。第 $i$ 头奶牛需要被降温 $c_i$，也就是说，它所占据的每个牛栏的温度都必须至少降低 $c_i$ 个单位。 牛棚里有 $M$ 台空调，编号为 $1 \ldots M$（$1 \leq M \leq 10$）。第 $i$ 台空调的运行费用为 $m_i$（$1 \leq m_i \leq 1000$），其制冷覆盖从牛栏 $a_i$ 到牛栏 $b_i$ 的区间。如果运行，第 $i$ 台空调会使该区间内所有牛栏的温度降低 $p_i$（$1 \leq p_i \leq 10^6$）。不同空调的覆盖区间可能相互重叠。 经营农场并不容易，FJ 的预算很紧。请你确定他需要花费的最少金额，以保证所有奶牛都感到舒适。保证当 FJ 使用所有空调时，所有奶牛都能满足需求。

输入格式

第一行输入包含 $N$ 和 $M$。 接下来 $N$ 行描述奶牛信息。第 $i$ 行包含 $s_i$、$t_i$ 和 $c_i$。 接下来 $M$ 行描述空调信息。第 $i$ 行包含 $a_i$、$b_i$、$p_i$ 和 $m_i$。 除样例外的所有输入，你可以假设 $M = 10$。

输出格式

输出一个整数，表示 FJ 为运行足够多的空调以满足所有奶牛（满足上述条件）所需花费的最小金额。

2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5

10

提示

一种使花费最少的可行方案是选择制冷区间为 $[2, 9]$、$[1, 2]$ 和 $[6, 9]$ 的空调，费用为 $3 + 2 + 5 = 10$。 题目鸣谢：Aryansh Shrivastava 和 Eric Hsu

标签: USACO|2023|Bronze

来源

USACO|2023|Bronze