P2887 [USACO07NOV]防晒霜Sunscreen

    • 773通过
    • 2.2K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 矩阵乘法 贪心 USACO 2007
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they're at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn't tan at all........

    The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPFi (1 ≤ SPFi ≤ 1,000). Lotion bottle i can cover coveri cows with lotion. A cow may lotion from only one bottle.

    What is the maximum number of cows that can protect themselves while tanning given the available lotions?

    有C个奶牛去晒太阳 (1 <=C <= 2500),每个奶牛各自能够忍受的阳光强度有一个最小值和一个最大值,太大就晒伤了,太小奶牛没感觉。

    而刚开始的阳光的强度非常大,奶牛都承受不住,然后奶牛就得涂抹防晒霜,防晒霜的作用是让阳光照在身上的阳光强度固定为某个值。

    那么为了不让奶牛烫伤,又不会没有效果。

    给出了L种防晒霜。每种的数量和固定的阳光强度也给出来了

    每个奶牛只能抹一瓶防晒霜,最后问能够享受晒太阳的奶牛有几个。

    输入输出格式

    输入格式:

    * Line 1: Two space-separated integers: C and L

    * Lines 2..C+1: Line i describes cow i's lotion requires with two integers: minSPFi and maxSPFi

    * Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPFi and coveri

    输出格式:

    A single line with an integer that is the maximum number of cows that can be protected while tanning

    输入输出样例

    输入样例#1: 复制
    3 2
    3 10
    2 5
    1 5
    6 2
    4 1
    输出样例#1: 复制
    2
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。