题目大意：有两颗苹果树，会一起掉苹果，某一秒一个人只能在一棵树下，移动次数有限，怎么移动可以捡取到更多的苹果（默认在1号树下）
原题链接http://poj.org/problem?id=2385
ac代码
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define maxn 1005 int dp[maxn][35],a[maxn],ans; int main() { int t,w; while(~scanf("%d%d",&t,&w)) { for(int i=1;i<=t;i++) { cin>>a[i]; } if(a[1]==1)//默认在1号树下面 { dp[1][0]=1; //d[i][j],i记录当前时刻，j记录移动次数 dp[1][1]=0; } else{ dp[1][1]=1; dp[1][0]=0; } for(int i=2;i<=t;i++) { for(int j=0;j<=w;j++) { if(j==0)dp[i][j]=dp[i-1][j]+a[i]%2;//当前在1：+1；在2：+0； else{ dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]); if(j%2+1==a[i])//当前位置时是否是苹果下落位置 dp[i][j]++; } } } for(int i=0;i<=w;i++) ans=max(ans,dp[t][i]); cout<<ans<<endl; } }
