1 条题解
-
0
题目分析
如果已经分好了队,对于每一队来说,最后吃完的人吃完的时间是
一定是按 降序排序更优,证明如下:
设 的前缀和为 ,假设最后排序方案存在 ,其中 ,那么
- 吃完的时间是
- 吃完的时间是
如果交换 ,则
- 吃完的时间是
- 吃完的时间是
容易发现前种情况两者取 max 不小于后种情况的两者取 max ,因此交换 一定不劣。
因此,我们将人按照 降序排序,设 表示考虑前 个人,第一队已经分配进去的人 的和是 ,转移如下
$$f_{i,j}=\min(\max(j+b_i,f_{i-1,j}),\max(s_i-j+b_i,f_{i-1,j}))$$可以去掉第一维,时间复杂度 。
- 1
信息
- ID
- 133
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者