A6266 | Welcome24ever 和奶牛
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
Welcome24ever 的 $N$ 头奶牛（$1\le N\le 20$）住在一个谷仓里，谷仓有连续的牛栏，编号 $1\sim 100$。奶牛 $i$ 占据牛栏区间 $[s_i,t_i]$，且不同奶牛的区间**互不相交**。奶牛 $i$ 占据的每个牛栏都要求温度至少降低 $c_i$ 单位。
谷仓里有 $M$ 台空调（$1\le M\le 10$）。若开启第 $i$ 台空调，需要花费 $m_i$ 金钱（$1\le m_i\le 1000$），它会使区间 $[a_i,b_i]$ 内**每个**牛栏的温度降低 $p_i$（$1\le p_i\le 10^6$）。空调区间可重叠、可覆盖多个奶牛区间。
请计算：为了满足**所有**奶牛在其各自区间内的降温要求，最少需要花费多少金钱。
谷仓里有 $M$ 台空调（$1\le M\le 10$）。若开启第 $i$ 台空调，需要花费 $m_i$ 金钱（$1\le m_i\le 1000$），它会使区间 $[a_i,b_i]$ 内**每个**牛栏的温度降低 $p_i$（$1\le p_i\le 10^6$）。空调区间可重叠、可覆盖多个奶牛区间。
请计算：为了满足**所有**奶牛在其各自区间内的降温要求，最少需要花费多少金钱。
输入格式
- 第一行：两个整数 $N,M$。
- 接下来 $N$ 行：每行三个整数 $s_i,t_i,c_i$。
- 再接下来 $M$ 行：每行四个整数 $a_i,b_i,p_i,m_i$。
- 接下来 $N$ 行：每行三个整数 $s_i,t_i,c_i$。
- 再接下来 $M$ 行：每行四个整数 $a_i,b_i,p_i,m_i$。
输出格式
- 一行一个整数：满足所有需求的**最小总花费**。
输入输出样例
输入 #1
2 4 1 5 2 7 9 3 2 9 2 3 1 6 2 8 1 2 4 2 6 9 1 5
输出 #1
10
## 样例解释
选择冷却区间为 $[2,9]$、$[1,2]$、$[6,9]$ 的三台空调，费用 $3+2+5=10$，可满足两段奶牛区间的降温需求。
## 数据范围
- $1\le N\le 20,\;1\le M\le 10$
- $1\le a_i,b_i,s_i,t_i\le 100$
- $1\le c_i,p_i\le 10^6,\;1\le m_i\le 1000$
选择冷却区间为 $[2,9]$、$[1,2]$、$[6,9]$ 的三台空调，费用 $3+2+5=10$，可满足两段奶牛区间的降温需求。
## 数据范围
- $1\le N\le 20,\;1\le M\le 10$
- $1\le a_i,b_i,s_i,t_i\le 100$
- $1\le c_i,p_i\le 10^6,\;1\le m_i\le 1000$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？