比起之前一直在刷的背包题，这道题可以算是最纯粹的dp了，写下简单题解。
题意是说cows在1树和2树下来回移动取苹果，有移动次数限制，问最后能拿到的最多苹果数，含有最优子结构性质，大致的状态转移也不难想出，以 dp[i][j] 表示第 i 分钟使用了 j 次移动机会时能获得的最多苹果数（不需3维，因为 j 隐含着在1树还是2树的信息，判奇偶性即可，一开始 0min 时在1树），大体的状态转移方程就是：
dp[i][j] = j & 1 ? c[i][2] : c[i][1] + max ( dp[i+1][j], dp[i+1][j+1] ) , if ( j<w )
+ dp[i+1][j] , else
上式中的 j&1 就是判断此时 dp[i][j] 是位于1树还是2树，把苹果下落位置用数组c[]记录下来（可以在草稿纸上直观地画出来），代码也就不难写出来了：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int dp[][];
bool c[][]; int main(){
int t,w,i,j,x;
while(~scanf("%d%d",&t,&w)){
memset(c,,sizeof(c));
for(i=; i<=t; ++i){
scanf("%d",&x);
c[i][x]= ;
}
for(j=; j<=w; ++j)
dp[t][j]= j&? c[t][]:c[t][];
for(i= t-; i>=; --i){
int tmp= min(i,w);
for(j=; j<=tmp; ++j){
dp[i][j]= j&? c[i][]:c[i][];
if(j<w) dp[i][j]+= max(dp[i+][j],dp[i+][j+]);
else dp[i][j]+= dp[i+][j];
}
}
printf("%d\n",max(dp[][],dp[][]));
}
return ;
}
我也看到有人用更精简的代码还有能把空间优化到一维的，但为了直观性，能让自己看懂，我也不想去折腾那些了，曾经的强迫症是时候要放一放了，全力刷题才是王道，看到自己那么一丁点儿的可怜的刷题量，和师兄几乎差了一个数量级的题量，对每一道题就不想大费周章地去追求尽善尽美了。