POJ 2385 Apple Catching

浏览数：24 / 时间：2015年06月11日

　　比起之前一直在刷的背包题，这道题可以算是最纯粹的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\n",max(dp[1][0],dp[1][1]));
28     }
29     return 0;
30 }