TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2915
  • 题目
  • P2915出租
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    问题描述

    明年1月到7月何老板将去环球旅行,在这期间,他打算把他在重庆的两套完全一样的房子租出去。现在有5个人想要租何老板的房子,他们的租期和愿意出的租金如下图所示:

    租房者	租期(从第x月租到第y月)	愿意出的租金
    甲	1月到2月                    	10
    乙	4月到7月                 	20
    丙	1月到3月	                    2
    丁	3月到7月	                    3
    茂	1月到6月	                    4
    


    何老板想得到尽可能多的租金,他该把房子租给哪些人呢?

    输入格式

    第1行:两个正整数,t表示何老板的房子从1月到t月可供出租,n表示租房者的人数
    接下来n行:每行三个正整数t1,t2,w, 分别表示第i个租房者的开始时间、结束时间和愿意出的租金隔。

    输出格式

    只有1行: 1个整数,表示能得到的最大租金。

    样例输入 1

    7 5
    1 2 10
    4 7 20
    1 3 2
    3 7 3
    1 6 4

    样例输出 1

    35

    样例输入 2

    288 8
    6 9 66
    28 185 52
    146 173 34
    129 225 35
    133 155 90
    138 175 57
    64 115 65
    223 260 59

    样例输出 2

    337

    样例输入 3

    24 10
    12 20 81
    4 4 17
    11 14 60
    1 20 13
    3 3 70
    10 17 31
    2 2 47
    7 11 27
    21 21 86
    4 9 76

    样例输出 3

    464

    提示

    样例1是这样实现的:第一套房子租给第1和第4个人,第二套房子租给第2和第3个人。这样最大的租金就为10+20+2+3=35。

    对于30%的数据:1<=t<=500 1<=n<=15 1<=w<=100 1<=t1<=t2<=t
    对于100%的数据:1<=t<=500 1<=n<=100 1<=w<=100 1<=t1<=t2<=t
    这里假设一年至少有t个月