P2690 [USACO04NOV] Apple Catching G

Few people know that cows love apples. There are two apple trees on Farmer John's farm (numbered $1$ and $2$), and both are laden with apples. Bessie the cow cannot pick apples from the trees, so she must wait for apples to fall. However, since apples that hit the ground get smashed, Bessie must catch them in midair (nobody likes smashed apples). Bessie eats quickly and can finish an apple within a few seconds after catching it. Every minute, exactly one of the two trees drops one apple. Bessie is well trained: as long as she stands under a tree, she is guaranteed to catch any apple that falls from that tree. She can move quickly between the two trees (the moving time is much less than $1$ minute), so when an apple falls, she will definitely be standing under one of the two trees. However, she is unwilling to keep running back and forth between the trees, so she may miss some apples. Apples fall once per minute for $T$ minutes ($1 \le T \le 1000$). Bessie is willing to move at most $W$ times ($1 \le W \le 30$). Given, for each minute, the index of the tree from which an apple falls, determine the maximum number of apples Bessie can catch. Initially, Bessie is under tree 1.

The first line contains 2 integers, $T$ and $W$. The next $T$ lines each contain one integer, indicating whether at that minute the apple falls from tree $1$ or tree $2$.

For each test case, output one line with a single integer: the maximum number of apples Bessie can catch.

Translated by ChatGPT 5