馒头馅的包子

馒头馅的包子

测试数据来自 wjszez/1676

【题目背景】
yk真的很喜欢吃,这点大家都知道~
不过,他不光喜欢吃糖果,还喜欢吃馒头,吃包子,吃玉米,吃南瓜,吃花生……yk
喜欢吃这么多东西,并且为了一次吃过瘾,他还发明了玉米馒头,南瓜馒头,花生
馒头……白馒头馅的包子,玉米馒头馅的包子,南瓜馒头馅的包子,花生馒头馅的包
子,玉米南瓜馒头馅的包子……后来,一个包子就变成了一个无敌巨无霸,中间塞了
玉米馒头、南瓜馒头、玉米南瓜馒头、南瓜花生馒头包子……包子里面塞馒头,包子
里面塞包子…… yk看着这些超级无敌巨无霸,心里真的好欢畅啊好欢畅~ 有这么多
好吃的~ yummy~
【问题描述】
现在yk身边只有N种馒头包子,包子里面包的可能是馒头也可能还是是包子 -_-||
每种包子有一个填饱程度c[i],yk的肚子只有M那么大,也就是yk吃的所有馒头包
子的填饱程度和不能大于M。每种包子还有一个美味程度系数v[i],则一个包子的
满足度为v[i]*c[i],yk想在不撑坏肚子的情况下得到最大的满足度。可是有的馒头虽然好吃,但是却是包在某个包子里面的,如果yk想吃到这个馒头,必须先吃掉
这个包子皮,不过好在包子皮里面最多只有两种馅,这样yk就不用担心包子太大吃
不下啦~ 现在yk想知道在满足上述所有条件的情况下,他最多能得到多少满足度。
【输入格式】
dumpling.in
第一行两个用空格隔开的正整数,M,N,分别表示yk肚子的大小和馒头馅的包子数

下面N行,每行3个整数c,v,k
第i+1行的三个整数c[i], v[i], k[i],c[i]表示馒头包子的填饱程度,v[i]
表示美味程度系数,k[i]=0表示你可以直接吃掉这个包子,否则k[i]表示如果要
吃这个馒头必须先吃掉第k[i]个包子的包子皮(一个包子皮里面最多包两种馅)
【输出格式】
dumpling.out
一行一个正整数,表示yk在不撑坏的情怀下最多能得到的满足度。
【样例】
dumpling.in
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
dumpling.out
2200
【数据范围】
100% M<32000, N<60, c<10000, v<6。保证答案不超过 200000

信息

ID
2086
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者