当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6475:商业竞争

题目描述
在这里你需要解决一个全世界人类从诞生起就面临的最大的问题——如何发大财。

你是一名电视广告市场的中介。你的工作是给要打广告的公司安排一天的时间去播放他们的广告。这家公司一共拍摄了$n$个广告片段,每个片段最多只能播放一次,第$i$个片段需要占据$w_i$秒的档期,在第$k$天这个片段给这家公司带来的净利润为$k\times a_i+b_i$。一个片段一旦开始播放就不能掐断。

你需要在$[l,r]$之间选择一个正整数$k$,在第$k$天播放这家公司的广告。这家公司在你告知$k$后,会斟酌着选择一些广告进行播放,使得他们的总收益最大(也可能一个广告都不播放,如果都是负收益的话)。电视每天最多只能播放总长度不超过$m$秒的广告,所以当档期不足时,他们也会酌情舍弃一些广告。

商业竞争是残酷的,对方赚的越多,你赚的就越少。请选择一个最合适的$k$,使得该公司按照最优策略投放广告的总收益最小。
输入解释
第一行包含一个正整数$T(1\leq T\leq 10)$,表示测试数据的组数。

每组数据第一行包含四个正整数$n,m,l,r(1\leq n,m\leq 500,1\leq l\leq r\leq 10^6)$,分别表示广告片段的数量、档期的限制以及选择的范围。

接下来$n$行,每行三个整数$a_i,b_i,w_i(-10^6\leq a_i\leq 10^6,-10^{12}\leq b_i\leq 10^{12},1\leq w_i\leq m)$,依次描述每个广告片段。
输出解释
对于每组数据输出一行一个整数,即该公司按照最优策略投放广告的总收益的最小可能值。
输入样例
1
3 5 1 5
-3 5 2
-2 2 3
2 5 3
输出样例
9
来自杭电HDUOJ的附加信息
Author Claris
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

题目来源 Championship

源链接: HDU-6475

最后修改于 2020-10-25T23:31:41+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000/1000MS(Java/Others) 65535/102400K(Java/Others)