比起之前一直在刷的背包题，这道题可以算是最纯粹的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[]记录下来（可以在草稿纸上直观地画出来），代码也就不难写出来了：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 int dp[1003][33]; 7 bool c[1003][3]; 8 9 int main(){ 10 int t,w,i,j,x; 11 while(~scanf("%d%d",&t,&w)){ 12 memset(c,0,sizeof(c)); 13 for(i=1; i<=t; ++i){ 14 scanf("%d",&x); 15 c[i][x]= 1; 16 } 17 for(j=0; j<=w; ++j) 18 dp[t][j]= j&1? c[t][2]:c[t][1]; 19 for(i= t-1; i>=1; --i){ 20 int tmp= min(i,w); 21 for(j=0; j<=tmp; ++j){ 22 dp[i][j]= j&1? c[i][2]:c[i][1]; 23 if(j<w) dp[i][j]+= max(dp[i+1][j],dp[i+1][j+1]); 24 else dp[i][j]+= dp[i+1][j]; 25 } 26 } 27 printf("%d ",max(dp[1][0],dp[1][1])); 28 } 29 return 0; 30 }
我也看到有人用更精简的代码还有能把空间优化到一维的，但为了直观性，能让自己看懂，我也不想去折腾那些了，曾经的强迫症是时候要放一放了，全力刷题才是王道，看到自己那么一丁点儿的可怜的刷题量，和师兄几乎差了一个数量级的题量，对每一道题就不想大费周章地去追求尽善尽美了。