在八百多年前的一天,Hang去约会女神,女神为了考验Hang,就决定考考他
Hang的女神把他带到了一个神奇的地方,这里一共有1~n的关卡,每种关卡只有两种,一种是0,一种是1
女神给了他两个背包,两个背包里面各有a,b瓶water,Hang每走一步都需要喝一瓶water
特别的是,如果Hang在关卡类型为1的时候,喝一瓶a的water,他会获得一瓶b的water(但是由于两个背包只能装各自的water,且两种背包只能装a,b瓶water,所以当b背包满的时候,是不会获得b类的water)
简单点说,如果在关卡类型为1的时候,喝一瓶a,如果b不是满的话,Hang会获得一瓶b
Hang想知道,如果以最优情况来走,Hang最远能走多远
Hang在每个关卡的时候,一定要喝一瓶water,如果喝完后,Hang没有water了,则Hang不能继续走了
第一行是3个整数n,a,b(3个范围都是1~2e5)
第二行是n个x[i](0或1)
输出一个整数,最远可以走多远(答案范围是1~n)
5 2 1 0 1 0 1 0 Hint: 1的时候喝一瓶b,剩下饮料数为2 0 2的时候喝一瓶a,剩下饮料数为1 1(在1的时候喝a,且b不是满的,获得一瓶b) 3的时候喝一瓶b,剩下饮料数为1 0 4的时候喝一瓶a,剩下饮料数为0 1 5的时候喝一瓶b,剩下饮料数为0 0
5
6 2 1 1 0 0 1 0 1
3 1 2 3的时候各喝一瓶 因为不会获得饮料 所以只能走到3