题意：

给你两个数字n和m；代表会有n个苹果掉落，m次可以移动的机会；有两棵树，开始你站在树1下面，一分钟只能移动一次，下面的数值代表在哪一颗树下会掉落苹果；问你在可移动的范围内，最多可以接到多少个苹果？

题目：

It is a little known fact that cows love apples. Farmer John has two apple trees (which are conveniently numbered 1 and 2) in his field, each full of apples. Bessie cannot reach the apples when they are on the tree, so she must wait for them to fall. However, she must catch them in the air since the apples bruise when they hit the ground (and no one wants to eat bruised apples). Bessie is a quick eater, so an apple she does catch is eaten in just a few seconds.

Each minute, one of the two apple trees drops an apple. Bessie, having much practice, can catch an apple if she is standing under a tree from which one falls. While Bessie can walk between the two trees quickly (in much less than a minute), she can stand under only one tree at any time. Moreover, cows do not get a lot of exercise, so she is not willing to walk back and forth between the trees endlessly (and thus misses some apples).

Apples fall (one each minute) for T (1 <= T <= 1,000) minutes. Bessie is willing to walk back and forth at most W (1 <= W <= 30) times. Given which tree will drop an apple each minute, determine the maximum number of apples which Bessie can catch. Bessie starts at tree 1.

Input

Line 1: Two space separated integers: T and W

Lines 2…T+1: 1 or 2: the tree that will drop an apple each minute.

Output

Line 1: The maximum number of apples Bessie can catch without walking more than W times.

Sample Input

7 2 2 1 1 2 2 1 1

Sample Output

6

Hint

INPUT DETAILS:

Seven apples fall - one from tree 2, then two in a row from tree 1, then two in a row from tree 2, then two in a row from tree 1. Bessie is willing to walk from one tree to the other twice.

OUTPUT DETAILS:

Bessie can catch six apples by staying under tree 1 until the first two have dropped, then moving to tree 2 for the next two, then returning back to tree 1 for the final two.

分析：

(1）.基础dp题,按照题意很容易看出有两个变量，分钟和移动机会，所以我们按照习惯写出两层for循环，简单思考其中的关系，就可以得到dp定义,$dp[i][j]$,表示在i时间内,用 $j$次转移机会得到的最大苹果数. (2).因为开始的位置在第一棵树下，那么我们就可以由移动的步数 $j$的奇偶性判断现在在哪颗树下； (3).dp转移如下,如果 $j==0$,则 $dp[i][j]=dp[i-1][j]$,考虑j为0时，到第i分钟，一步都没有走动。 否则 $dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])$.就是当前从上一个状态下，走还是不走获得苹果最多。 (4)如果现在所在的树的编号和现在掉落的苹果所在的位置相同，那么接到的苹果的数量姐增加，由（2）这个我就放在最后判断一下就行，也可以放在第三步，直接在推导式里面。 (5).最后在 $dp[n][i]$里找最大值就行了,$(0<=i<=n).$表示一共走i步时，n分钟吃到苹果最大值。 我今天真的闲的罗里吧嗦这么多，自恋的觉得只要跟着我的思路走，一定能会这道题，hhh

AC模板：

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int M=1e3+10; int n,m,ans; int s[M],dp[M][35]; int main() { while(~scanf("%d%d",&n,&m)) { ans=0; memset(dp,0,sizeof(dp)); for(int i=1; i<=n; i++) scanf("%d",&s[i]); if(s[1]==1) dp[1][0]=1; else dp[1][1]=1; for(int i=2; i<=n; i++) for(int j=0; j<=i&&j<=m; j++) { if(j==0)//考虑j为0时，也就是说，到第i分钟，一步都没有走动。 dp[i][j]=dp[i-1][j]+s[i]%2; else { dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);//就是当前走还是不走获得苹果最多。 if(j%2+1==s[i])//因为最开始站在树1下面，可以用走多少步的奇偶来表示当前在那棵树下。 dp[i][j]++; } } for(int i=0; i<=m; i++)//表示一共走i步时，n分钟吃到苹果最大值。 ans=max(ans,dp[n][i]); printf("%d\n",ans); } return 0; }

备战ccpc分站赛ing ，题目分析简略，见谅，转载请注明出处。。。。。