P2207 Photo

    • 217通过
    • 578提交
  • 题目提供者 韦索宇韦
  • 评测方式 云端评测
  • 标签 搜索 USACO
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Framer Jhon 打算给他的N头奶牛照相,( 2 <= N <= 1 000 000 000) 。

    他们排成一条线,并且依次取1~N作为编号。

    每一张照片可以拍摄到这列奶牛中一个连续的区间中的奶牛。

    对于每一头奶牛,FJ都想要让Ta至少出现在一张照片里。

    不幸的是,有K对关系不好的奶牛( 1 <= K <= 1000),他们拒绝出现在同一张照片里。

    已知所有关系不好的奶牛所在的位置,请计算出FJ需要的最小需要拍摄的照片数量。

    输入输出格式

    输入格式:

    *第一行: 两个整数: N,K.

    *第2..K+1行中,第i+1行有两个整数,记为A_i与B_i。它们代表着处在队列中第A_i头奶牛与第B_i头奶牛是关系不好的,它们不能出现在同一张照片里。

    输出格式:

    *一个整数,代表FJ需要的最小需要拍摄的照片数量

    输入输出样例

    输入样例#1: 复制
    7 3
    1 3
    2 4
    5 6
    
    输出样例#1: 复制
    3

    说明

    输出解释:FJ可以只拍三张照片:[1,2] , [3,5] , [6,7]

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