题意分析

在 $T$ 分钟内，两棵苹果树会依次掉落苹果，每分钟只有一棵树上的苹果掉落。贝西初始站在 1 号树下，她最多可以在两棵树之间移动 $W$ 次，每次移动能让她站到另一棵树下。她只有站在掉苹果的树下才能接住苹果，求她最多能接住的苹果数。

解题思路

使用动态规划来解决此问题。定义状态 $dp[i][j]$ 表示在前 $i$ 分钟内移动了 $j$ 次所能接住的最多苹果数。通过分析不同的移动情况，得出状态转移方程，最终找出最大的 $dp[T][j]$（$0\leq j\leq W$）。

分析

1.因为贝西的移动次数有限，且每分钟的状态依赖于之前的状态，所以适合用动态规划来求解。

2.状态转移时需要考虑两种情况：不移动和移动一次，同时判断当前是否能接住苹果。

实现步骤

1.读取输入的 T 和 W，以及每分钟掉苹果的树的编号。

2.初始化边界条件，如 dp[1][0] 和 dp[1][1] ，以及 dp[i][0]。

3.对于 i 从 2 到 T，j 从 1 到 W，根据状态转移方程更新 dp[i][j]。

4.遍历 dp[T][j]（0≤ j≤ W），找出最大值作为结果。

代码实现

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>

using namespace std;

int s[1005]= {0};
int dp[1005][35]= {0};

int main()
{
    //freopen("in.in","r",stdin);
    int t, w;
    while(scanf("%d%d",&t,&w)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        memset(s,0,sizeof(s));
        for(int i=1; i<=t; i++)
            scanf("%d",&s[i]);
        
        if(s[1]==1)dp[1][0]=1;//对i=1的情况初始化
        else dp[1][1]=1;
        
        for(int i=2; i<=t; i++)
            dp[i][0]=dp[i-1][0]+s[i]%2;//对j=0的情况初始化
        
        for(int i=2; i<=t; i++)
            for(int j=1; j<=w; j++)
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);//状态转移
                if((s[i]+1)%2==j%2)dp[i][j]++;//如果此时恰好在果树下，还可再吃一个苹果
            }
        int max_n=0;
        for(int i=1;i<=t;i++)
            if(dp[i][w]>max_n)max_n=dp[i][w];
        printf("%d\n",max_n);
    }
    return 0;
}

代码说明

1.s[i] 数组存储第 i 分钟掉苹果的树的编号。

2.dp[i][j] 表示在前 i 分钟内移动了 j 次所能接住的最多苹果数。

3.初始化部分处理了 (i = 1) 和 (j = 0) 的特殊情况。

4.状态转移方程 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]) 考虑了不移动和移动一次的情况。

5.if((s[i]+1)%2==j%2)dp[i][j]++ 用于判断当前是否能接住苹果。

6.最后遍历找出 (dp[i][W]) 中的最大值作为结果输出。