首先声明：( ext{POJ}) 数据出错，搞成了“一开始在 (1) 或 (2) 棵树都可以”，导致错误。事实上本题解可以通过。
听说还有一维 ( ext{dp}) 的啊，相当厉害，可我只会三维的。
考虑令 (f_{i,j,1/2}) 表示第 (i) 分钟，经过 (j) 次移动后站在第 (1 / 2) 棵树位置时摘到的最大苹果数。分类讨论：
从 (2/1 ightarrow 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
",i,j,f[i][j][1],f[i][j][2]);
} printf("%d
",ans);
return 0;
}