P3118 [USACO15JAN]电影移动Moovie Mooving

    • 166通过
    • 619提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 单调队列 状态压缩,状压 USACO 2015 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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).

    奶牛贝西想连续看L (1 <= L <= 100,000,000)分钟的电影,有 N (1 <= N <= 20)部电影可供选择,每部电影会在一天的不同时段放映。

    贝西可以在一部电影播放过程中的任何时间进入或退出放映厅。但她不愿意重复看到一部电影,所以每部电影她最多看到一次。她也不能在看一部电影的过程中,换到另一个正在播放相同电影的放映厅。

    请帮贝西计算她能够做到从0到L分钟连续不断地观看电影,如果能,请计算她最少看几部电影就行了。

    输入输出格式

    输入格式:

    INPUT: (file movie.in)

    The first line of input contains N and L.

    The next N lines each describe a movie. They begin with its integer duration, D (1 <= D <= L) and the number of showtimes, C (1 <= C <= 1000). The remaining C integers on the same line are each in the range 0..L, and give the starting time of one of the showings of the movie. Showtimes are distinct, in the range 0..L, and given in increasing order.

    输出格式:

    UTPUT: (file movie.out)

    A single integer indicating the minimum number of movies that Bessie

    needs to see to achieve her goal. If this is impossible output -1

    instead.

    输入输出样例

    输入样例#1: 复制
    4 100 
    50 3 15 30 55 
    40 2 0 65 
    30 2 20 90 
    20 1 0 
    
    输出样例#1: 复制
    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.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。