Air Cownditioning II
실버 II의견: 0
With the hottest recorded summer ever at Farmer John's farm, he needs a way to
cool down his cows. Thus, he decides to invest in some air conditioners.
Farmer John's \(N\) cows (\(1 \leq N \leq 20\)) live in a barn that contains a
sequence of stalls in a row, numbered \(1 \ldots 100\). Cow \(i\) occupies a range
of these stalls, starting from stall \(s_i\) and ending with stall \(t_i\). The
ranges of stalls occupied by different cows are all disjoint from each-other.
Cows have different cooling requirements. Cow \(i\) must be cooled by an amount
\(c_i\), meaning every stall occupied by cow \(i\) must have its temperature reduced
by at least \(c_i\) units.
The barn contains \(M\) air conditioners, labeled \(1 \ldots M\)
(\(1 \leq M \leq 10\)). The \(i\)th air conditioner costs \(m_i\) units of money to
operate (\(1 \leq m_i \leq 1000\)) and cools the range of stalls starting from
stall \(a_i\) and ending with stall \(b_i\). If running, the \(i\)th air conditioner
reduces the temperature of all the stalls in this range by \(p_i\)
(\(1 \leq p_i \leq 10^6\)). Ranges of stalls covered by air conditioners may
potentially overlap.
Running a farm is no easy business, so FJ has a tight budget. Please determine
the minimum amount of money he needs to spend to keep all of his cows
comfortable. It is guaranteed that if FJ uses all of his conditioners, then all
cows will be comfortable.
Problem credits: Aryansh Shrivastava and Eric Hsu
Problem credits: Aryansh Shrivastava and Eric Hsu
The first line of input contains \(N\) and \(M\).
The next \(N\) lines describe cows. The \(i\)th of these lines contains \(s_i\),
\(t_i\), and \(c_i\).
The next \(M\) lines describe air conditioners. The \(i\)th of these lines contains
\(a_i\), \(b_i\), \(p_i\), and \(m_i\).
For every input other than the sample, you can assume that \(M = 10\).
Output a single integer telling the minimum amount of money FJ needs to spend to
operate enough air conditioners to satisfy all his cows (with the conditions
listed above).
2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 510One possible solution that results in the least amount of money spent is to
select those that cool the intervals \([2, 9]\), \([1, 2]\), and \([6, 9]\), for a
cost of \(3 + 2 + 5 = 10\).
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > January > Bronze
평가 및 의견
Air Cownditioning II
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Air Cownditioning II