#PU515. USACO 2015 January Contest, Gold — Problem 2. Moovie Mooving

    ID: 1444 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan15来源:usaco.orgscoring:equal_test_cases贪心

USACO 2015 January Contest, Gold — Problem 2. Moovie Mooving

USACO 2015 January Contest, Gold — Problem 2. Moovie Mooving

题目描述

Problem 2: Moovie Mooving [Lewin Gan and Mark Gordon, 2015]

Bessie is out at the movies. Being mischievous as always, she has decided to hide from Farmer John for L (1 <= L <= 100,000,000) minutes, during which time she wants to watch movies continuously. She has N (1 <= N <= 20) movies to choose from, each of which has a certain duration and a set of showtimes during the day. Bessie may enter and exit a movie at any time during one if its showtimes, but she does not want to ever visit the same movie twice, and she cannot switch to another showtime of the same movie that overlaps the current showtime.

Help Bessie by determining if it is possible for her to achieve her goal of watching movies continuously from time 0 through time L. If it is, determine the minimum number of movies she needs to see to achieve this goal (Bessie gets confused with plot lines if she watches too many movies).

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 100
50 3 15 30 55
40 2 0 65
30 2 20 90
20 1 0
3

SOLUTION NOTES:

Bessie should attend the first showing of the fourth movie from time 0
to time 20.  Then she watches the first showing of the first movie
from time 20 to time 65.  Finally she watches the last showing of the
second movie from time 65 to time 100.