PID318 / [汪老师搬水]生命在于运动
题目描述

背景:话说雅礼中学信息组那相貌堂堂一表人才身强力壮却筋骨疏懒的汪老师结婚后,一改从前酱油瓶子倒了都不扶的懒得要死的习气。曾经那个十指不沾阳春水的他已经一去不复返了(这个……),取而代之的是整天对老婆无事献殷勤、捏肩捶腿、里外包办的居家好男人!(无语了吧……)性格也改了许多,让我们这些做学生的只能以一种蹲着的状态瞻仰他!

为了使他的老婆更健康、美丽,汪老师选择用消毒饮水机外加桶装纯净水。但是这也出现了一个问题:搬水!

这一天,我们这位好男人在家闲着没事,正和老婆看电视呢,突然——他的老婆用神奇的女高音尖叫一声:“啊!!!!家里没水了!”

聚精会神看电视汪老师被吓了一大跳!!三魂七魄被抽去了一魂一魄!!(厉害!)

但是他的智力还是没问题的,他立即打电话给送水公司一次叫了N(3<=N<=20)桶水!(这样还说智力没问题?)不一会儿送水公司的人就到了楼底下,就等着往上搬水了.这时候,汪老师抓住机会要好好表现一下了!!

机灵的汪老师灵机一动,自己下去搬水!只见他“嗖”的一声,穿上了他的万年不变的老凉拖,冲下T(1<=T<=50)层楼(他家就住这么高……)可是到了底下才发觉,这个水不是那么好搬的……他又抬头望望楼上老婆那期待的眼神……他无畏地笑笑,冲老婆大喊:

“生命在于运动!”

无奈,快乐是留给别人的,痛苦是留给自己的。那个在科技楼帮自己搬水的超级壮汉Anyone又不在身边,没人使唤,只有靠自己啦!

--------------------------------------------------

首先设汪老师本人(不带水桶)移动一层算作一次操作。

初始状态时,汪老师和所有的水桶都在一楼。

每一个水桶i都有自己的最大移动量Mi(1<=i<=N),即这桶水在汪老师手中可以移动1..Mi(1<=Mi<=T)层,汪老师本人可以一次最多抬起P(1<=p<=10)桶水上楼,当最后一个水桶放下时算这一次操作完成。当手中的一桶水不能再上楼时,汪老师会将其放下,而不会影响其它的水桶的操作。手中有水时经过一层楼,如果这层楼有水,因汪老师力量有限,即使汪老师手中的水桶数不满P,也不能再搬这层楼的水,如果汪老师硬要搬,则算另一次操作。

问汪老师经过几次操作后,可以将所有的水都搬上T楼?

-------------------------------------------------汪老师累得满头大汗!各位好心的OIer,帮帮可怜的汪老师吧!

P.S.因算法不确定,设为“其他”。

输入格式

两行:

第一行为三个整数:N,T,P

第二行为N个整数,每一个整数用一个空格隔开,分别表示M1..Mn。

输出格式

一行,即最小操作次数(即汪老师的最少上下楼数)。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论