| 题目名称 | 1042. [Clover S2] Freda的烦恼 |
|---|---|
| 输入输出 | freda1.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-08-23加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：13， 提交：45， 通过率：28.89% | ||||
 wangyucheng |
100 | 0.106 s | 0.31 MiB | C++ |
 好坑呀 |
100 | 0.109 s | 0.29 MiB | C++ |
|
好坑呀 |
100 | 0.109 s | 0.29 MiB | C++ |
 Ezio |
100 | 0.110 s | 0.31 MiB | C++ |
 devil |
100 | 0.116 s | 3.36 MiB | C++ |
 QhelDIV |
100 | 0.125 s | 0.31 MiB | C++ |
 临轩听雨ゐ |
100 | 0.138 s | 3.37 MiB | C++ |
 Justpenz233 |
100 | 0.146 s | 3.67 MiB | C++ |
 Makazeu |
100 | 0.355 s | 0.32 MiB | C++ |
|
Justpenz233 |
100 | 0.359 s | 3.67 MiB | C++ |
| 关于 Freda的烦恼 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
最后数据居然是longlong。。。尼玛
 Launcher
2013-10-27 11:27
1楼
| ||||
-
题目叙述
Freda 的旅行社开通了一条暑期旅行路线，路线可以被看成是一条直线。这条路线一共
经过N 个地区，N 个地区的管辖范围完全覆盖了整条旅行路线且管辖范围之间两两没有重合。
我们知道，地区与地区之间的气温可能是不同的，第i 个地区的气温设为ti.报名旅行
的M 名游客都要乘车从第1 个地区前往第N 个地区,每辆车的容量没有限制。当然，谁也不想
让自己乘坐的车里温度太高。假设经过第i 个地区的时候，一辆车上面有k 名乘客，那么这
辆车上的温度就是ti+k。如果某辆车上的温度超过了这个地区的“最热限制”Ti(ti+k>Ti)，
这辆车上的每个乘客都会向旅行社索赔xi 元钱，用法律武器维护自己合法权益。
还有很特殊的一点，游客所乘坐的车不是从1~N 直达的，而是在各个地区分别租用的。
在第i 个地区租用的车只能在第i 个地区的管辖范围内行驶。即进入第i 个地区时，租用第
i 个地区的车，离开第i 个地区时，就要继续租用第i+1 个地区的车。在第i 个地区，你可
以租用任意数量的车，租用一辆车的费用是ci。
下面，Freda 请你帮忙设计一个花费最小的方案，即设计在每个地区的租车数目以及此
时安排到每辆车上的乘客数目。这个方案的花费是租车费用+给乘客的赔偿金（如果有的话）,
输出这个最小花费。
输入格式
第一行两个整数N，M，表示地区数目和乘客数目。
接下来N 行每行4 个整数，第i 行的4 个整数表示ti,Ti,xi,ci.含义如上所示。
输出格式
一行一个整数表示最小花费。
输入样例
2 10
30 35 1 100
20 35 10 10
输出样例
120
样例解释
在第1 个地区，租用1 辆车，车内温度为30+10=40>35，需要给乘客每人1 元补偿费。
在第2 个地区，租用1 辆车，车内温度为20+10=30<35，不需要给乘客补偿费。
总费用为100（第一个地区的租车费用）+10（第二个地区的租车费用）+10（第一个地
区的补偿费用）=120.
数据范围与约定
对于50%的数据，N<=100, M<=100.
对于100%的数据，0