首先声明：\(\text{POJ}\) 数据出错，搞成了“一开始在 \(1\) 或 \(2\) 棵树都可以”，导致错误。事实上本题解可以通过。
听说还有一维 \(\text{dp}\) 的啊，相当厉害，可我只会三维的。
考虑令 \(f_{i,j,1/2}\) 表示第 \(i\) 分钟，经过 \(j\) 次移动后站在第 \(1 / 2\) 棵树位置时摘到的最大苹果数。分类讨论：
从 \(2/1 \rightarrow 1/2\)，此时答案为 \(f_{i-1,j-1,2/1}\).
保持不动，则此时答案为 \(f_{i-1,j,1/2}\).
要注意什么时候可以拿到当前的苹果：因为有些状态是不存在的（就你偶数次移动一定是在 \(1\)，奇数次在 \(2\)），因此注意移动次数和苹果位置的综合判断。
还有一点，不是移动次数越多，拿到的苹果就越多。如果 \(a_i = 1(\forall i \in [1,T])\)，那么一次不动才是最好的，并不是动很多次。
时间复杂度：\(\mathcal{O}(TW)\).
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=1e3+1;
inline int read(){char ch=getchar(); int f=1; while(ch<‘0‘ || ch>‘9‘) {if(ch==‘-‘) f=-f; ch=getchar();}
int x=0; while(ch>=‘0‘ && ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar(); return x*f;}
inline void write(int x) {
if(x<0) {putchar(‘-‘);write(-x);return;}
if(x<10) {putchar(char(x%10+‘0‘));return;}
write(x/10);putchar(char(x%10+‘0‘));
}
int T,W,a[N];
int f[N][31][2];
int main() {
T=read(),W=read();
for(int i=1;i<=T;i++) a[i]=read();
int ans=0;
for(int j=0;j<=W;j++)
for(int i=1;i<=T;i++)
for(int j=0;j<=W;j++) {
f[i][j][1]=max(f[i-1][j-1][2],f[i-1][j][1])+(a[i]==1 && j%2==0);
f[i][j][2]=max(f[i-1][j-1][1],f[i-1][j][2])+(a[i]==2 && j%2==1);
ans=max(ans,max(f[i][j][1],f[i][j][2]));
// printf("%d %d %d %d\n",i,j,f[i][j][1],f[i][j][2]);
} printf("%d\n",ans);
return 0;
}