问题 25630 --抓苹果

25630: 抓苹果

时间限制: 1 Sec  内存限制: 128 MB
提交: 61  解决: 30
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][92kb]

题目描述

告诉你一个鲜为人知的事实:奶牛喜欢吃苹果。农夫约翰有编号为 1 2 的两棵苹果树,每棵树上都结满了苹果。贝西够不着树上的苹果,所以她必须等它们落到地上。然而,她必须在苹果落地之前接住它们(苹果掉在地上就被摔坏了,没有人爱吃坏苹果)。贝西吃东西的速度很快,可以在几秒钟内吃完一只苹果。

    在每一分钟,两棵苹果树中的一棵会掉下一只苹果。贝西训练有素,只要她站在树下就能接到掉下来的苹果。尽管贝西可以快速地在两棵树之间行走(远不需要一分钟),但是她每一分钟只能站在一棵树下。此外,由于奶牛们的运动训练不足,所以她不高兴在两棵树之间无止尽地走来走去,就算这样就失去一些苹果也一样。

    每分钟掉落一个苹果,一直会持续T (1 T 1000)分钟,贝西最多愿意来回奔波W (1 W 30)次。给出每分钟苹果掉落地情况,确定贝西可以抓到的最大苹果数量。贝西一开始在 1 号树下。

输入

第一行:两个用空格分开的整数:TW

第二行到第T + 1行:表示在这一分钟内哪棵树上的苹果将掉落

输出

第一行:贝西在移动不超过W次的条件下能够抓到的最大苹果数量

样例输入

7 2 
2 
1 
1 
2 
2 
1 
1

样例输出

6

提示

(一共有七个苹果,第一个从 2 号树上掉落,(贝西可以抓住六个苹果:首先待在 1 号树其次是 1 号树上掉落两个,接下来是 2 号树上掉落两个,最后 1 号树上落下最后两个,而贝西只想移动两次)下得到两个,再移动到 2 号树下抓住两个,再返回 1 号树,抓住最后两个)

来源

[提交][状态]