POJ 2385

经典DP。
设dp[i][j]为前i分钟移动j次所得的最大苹果数，本来打算再设一状态表示当前在哪棵树，但发现移动的次数就能确定了。
dp[i][j]=max(dp[i-1][k-1]+catc(k%2,app[i]),dp[i-1][k]+catc(k%2,app[i]));
 1 #include <iostream>                                                                      
 2 #include <cstdio>                                                                        
 3 using namespace std;                                                                     
 4                                                                                          
 5 const int MAX=1010;                                                                      
 6 int dp[MAX][40],app[MAX];                                                                
 7 int T,W;                                                                                 
 8                                                                                          
 9 int catc(int a,int b){                                                                   
10     if(a==b) return 1;                                                                      
11     return 0;                                                                               
12 }                                                                                        
13                                                                                          
14 int main(){                                                                              
15     int t;                                                                                  
16     while(scanf("%d%d",&T,&W)!=EOF){                                                        
17         for(int i=1;i<=T;i++){                                                                 
18             scanf("%d",&t);                                                                       
19             app[i]=t-1;                                                                           
20         }                                                                                      
21         memset(dp,-1,sizeof(dp));                                                              
22         dp[0][0]=0;                                                                            
23         for(int i=1;i<=T;i++){                                                                 
24             dp[i][0]=dp[i-1][0]+catc(0,app[i]);                                                   
25         }                                                                                      
26         for(int i=1;i<=T;i++){                                                                 
27             for(int k=1;k<=W;k++){  
28                 if(dp[i-1][k-1]>=0)                                                              
29                 dp[i][k]=dp[i-1][k-1]+catc(k%2,app[i]);   
30                 if(dp[i-1][k]>=0)  
31                 dp[i][k]=max(dp[i][k],dp[i-1][k]+catc(k%2,app[i]));     
32             }                                                                                     
33         }                                                                                      
34         int ans=0;                                                                             
35         for(int i=0;i<=W;i++)                                                                  
36         ans=max(ans,dp[T][i]);                                                                 
37         printf("%d
",ans);                                                                    
38     }                                                                                       
39     return 0;                                                                               
40 }
View Code