TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  训练指南  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3093
  • 题目
  • P3093盒子涂色
    限制 : 时间限制 : 10000 MS   空间限制 : 165536 KB
    评测说明 : 1s,128m
    问题描述

    有n个盒子排成一行,编号1到n。一开始,所有的盒子都是黑色的。
    有如下两种操作:
    “1 ai xi”:你可以从编号1到ai间( [1,ai] )的黑盒子中任选xi个,将它们涂成白色;
    “2 ai xi”:你可以从编号ai到n间( [ai,n] )的黑盒子中任选xi个,将它们涂成白色;
    给出若干操作的序列,问最多能得到多少个白色的盒子?
    得到最多的白色盒子最少需要使用多少个操作?
    注意:
    1.对于给出的操作,不一定要按给出的顺序执行。
    2.每个操作,你都可以选择使用,也可以不使用它。
    3.若一个操作对应的区间中没有足够的黑盒子,该操作将无法进行。

    输入格式

    第一行,两个整数n和m,表示有n个盒子,m个操作。
    接下来m行,每行三个整数 si(1<=si<=2) , ai , xi (0 <= xi <= n,1<=ai<=n),
    si代表操作的类型, ai和xi如题目描述。

    输出格式

    一行,两个空格间隔的整数,第一个表示最多能得到的白色盒子数,第二个表示最少所需的操作数。

    样例输入 1

    样例1:
    5 2
    2 3 3
    1 3 3

    样例2:
    10 6
    2 10 2
    2 9 3
    1 5 4
    2 5 1
    1 6 2
    2 8 0

    样例输出 1

    样例1:
    3 1

    样例2:
    7 3

    样例输入 2

    30 10
    1 7 4
    2 4 3
    1 24 2
    1 10 4
    1 21 2
    1 23 3
    1 16 2
    2 30 0
    1 18 2
    1 8 3

    样例输出 2

    22 8

    提示

    【样例2解释】
    采用了下列三个操作
    1 5 4
    2 5 1
    1 6 2
    操作1 5 4和1 6 2 将1到6全部涂成了白色
    操作2 5 1 在7到10间任选一个涂成了白色
    总共7个白色
    【数据范围】
    1 <= N <= 1000 , 1<=M<=1000


    来源  hdu4381