ZUFEOJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
Login
Register
6729: 机器人小Q
内存限制:125 MB
时间限制:1 S
题面:传统
评测方式:文本比较
上传者:
提交:1
通过:1
提交
提交记录
统计
Web Board
题目描述
成功派送完这个大单后,餐厅决定引入一名新成员:机器人小 Q。小 Q 的到来让餐厅的客源增加了不少,但是,一段时间之后,新的问题又出现了,小 Q 和我们可不一样,如果要让他工作的话,我们得给他输入能量以保持体力,而小 Q 的能量菜单表上已经按一定顺序给出了 $N$ 个单位的能量值,但是每个单位的能量由于来源不同,需要消耗一定的时间摄入。已知小 Q 每天充电的时间上限值为 $119$,如果时间超出的话就会自动崩溃,大家都想让小 Q 留下来,经过研究之后,决定派 HWX 和 XYF 去和老板谈判,考虑角度不一样,LXC 老板才不想听什么辛酸流泪史,他只想知道,若是想让小 Q 获得 $k$ 单位的能量(也就是能量表中可以不接受某些能量)最少需要几天来充电。
输入格式
第一行,两个整数,$N,K$ 分别表示小 Q 的能量菜单上有 $N$ 个单位的能量,想获取其中的 $k$ 个。
第二行,$N$个整数,分别是第 $i$ 个单位能量需要的充电时间。
输出格式
仅一行,一个整数,为最少需要天数。
如果永远不能达到题目要求,输出 `You can't do it.`
输入样例
复制
7 3 1 119 119 1 120 120 118
输出样例
复制
2
数据范围与提示
### 样例解释
只接收 $1,1,118$。显然这需要 $2$ 天。
### 数据规模
对于 $30\%$ 的数据,有 $1\le K\le N\le 20$。
对于 $100\%$ 的数据,有 $1\le K\le N\le 3000$。
分类标签
dp
普及+/提高