有两棵苹果树，有T个时刻，每个时刻给出苹果从哪棵树上掉落，如果人在该苹果树下就会得到一个苹果，人最多移动W步，并不确定人一开始在哪颗树下，求人最多能得到多少个苹果。
显然DP。 那么状态就是：当前时刻移动过多少步，在哪棵苹果树下，得到了多少苹果。//读者看到这里推荐可以自己想如何状态转移。
so, DP[ i ][ j ][ k ]代表第 i 时刻，移动了 j 步，在编号 k 苹果树下，得到了DP[ i ][ j ][ k ]个苹果。 所以，我每次要更新哪些状态： 1. 当前时刻在编号 1 树下，移动 t ∈min{i ,W} 步下的最大步数 2. 当前时刻在编号 2 树下，移动 t ∈min{i ,W} 步下的最大步数 怎么转呢？ 对于当前树，无非就是之前就在当前树下，或者从另外一棵树下来的，然后看看当前树有没有苹果掉下来 关于具体写法优化，dp的第一维可以利用滚动数组。 。 Code：
//#include <bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstring> #include<stack> #include<set> #include<map> #include<queue> #include<math.h> #include<algorithm> typedef long long LL; using namespace std; //#pragma comment(linker, "/STACK:102400000,102400000") const int N=1e3+10; int dp[2][35][2],t[N]; int n,w; void solve(){ int now=0; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ now = 1 - now; if(t[i] == 1){ dp[now][0][0]=dp[1-now][0][0]+1; for(int j=1;j<=w && j<=i;j++){ dp[now][j][0]=max(dp[1-now][j][0],dp[1-now][j-1][1])+1; dp[now][j][1]=max(dp[1-now][j][1],dp[1-now][j-1][0]); } } else { dp[now][0][1]=dp[1-now][0][1]+1; for(int j=1;j<=w && j<=i;j++){ dp[now][j][0]=max(dp[1-now][j][0],dp[1-now][j-1][1]); dp[now][j][1]=max(dp[1-now][j][1],dp[1-now][j-1][0])+1; } } } int ans=0; for(int i=1;i<=w;i++){ ans = max(ans,dp[now][i][0]); ans = max(ans,dp[now][i][1]); } printf("%d\n",ans); } int main(){ scanf("%d%d",&n,&w); for(int i=1;i<=n;i++) scanf("%d",&t[i]); solve(); return 0; }