#P3384. [Usaco2004 Nov]Apple Catching 接苹果

    ID: 2574 传统题 1000ms 512MiB 尝试: 133 已通过: 89 难度: 3 上传者: 标签>难度分类普及动态规划线性 DP状态维度消除滚动数组CF1300Gold

[Usaco2004 Nov]Apple Catching 接苹果

[USACO 2004 Nov] Apple Catching 接苹果

题目描述

农夫约翰的田里有两棵苹果树,编号为 11 和 22。贝茜够不到树上的苹果,只能在苹果掉到地上之前把它接住。她吃苹果很快,不会影响她接下一个苹果。

连续 TT 分钟,每分钟恰有一棵树掉下一个苹果。如果贝茜当时站在这棵树下,她就能接住。她可以在两次苹果掉落之间从一棵树走到另一棵树,也可以在第一个苹果掉落前移动。开始时,她在 11 号树下;总共最多移动 WW 次。

给定每分钟掉下苹果的树,求贝茜最多能接住多少个苹果。

输入格式

从标准输入读入。第一行是两个整数 T,WT,W。接下来 TT 行,每行一个整数 11 或 22,表示该分钟掉下苹果的树。

输出格式

向标准输出输出一行一个整数,表示最多能接住的苹果数。

7 2
2
1
1
2
2
1
1
6

样例解释

贝茜留在 11 号树下,先接住第 2,32,3 分钟掉落的两个苹果,再到 22 号树下接住第 4,54,5 分钟的两个苹果,最后回到 11 号树下接住剩下两个。

数据范围与约定

1≤T≤1 0001\le T\le1\,000,1≤W≤301\le W\le30。