http://poj.org/problem?id=2385
题目大意：
有两棵树，一开始站在第一棵树，每秒有苹果从树上掉下（不会同时两棵树都有），你最多移动w次，求t秒后你能得到的最大的苹果数目。
思路：
设d[i][j]表示第i个苹果移动j次能获得的最大苹果数 。
则 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);
如果当前的位置有苹果则dp[i][j]++
如何确定当前位置？因为就在两棵树间移动，所以根据奇偶性即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1024;
int dp[MAXN][35];//d[i][j]表示第i个苹果移动j次能获得的最大苹果数
int apple[MAXN],cur[MAXN];
int main()
{
cur[0]=1;
for(int i=1;i<=30;i++)
{
if(i&1)
cur[i]=2;
else
cur[i]=1;
}
int t,w;
while(~scanf("%d%d",&t,&w))
{
dp[0][0]=0;
for(int i=1;i<=t;i++)
{
scanf("%d",&apple[i]);
dp[i][0]=dp[i-1][0]+ (apple[i]==1?1:0);
//一开始写app[i]==cur[i]跪了。。。 应该是不动的时候可以获得的，也可以是cur[0]
//当然cur[0]=1
}
for(int i=1;i<=t;i++)
{
for(int j=1;j<=w;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);
//如果当前苹果i的位置apple[i]与现在所站的位置相同，可以拿一个苹果
if(cur[j]==apple[i])
dp[i][j]++;
}
}
int ans=0;
for(int i=0;i<=w;i++)
ans=max(dp[t][i],ans);
printf("%d\n",ans);
}
return 0;
}