本文共 1657 字，大约阅读时间需要 5 分钟。
dp[T,W,N]: 在T分钟，移动次数剩余W次时，在第N棵树下可以拿到的苹果的最大数量。
简化： 一开始因为奶牛是在第一棵树，而苹果树只有两棵，因此奶牛的位置可以由剩余移动次数W来确定，故 dp[T,W,N] → dp[T,W]: 在T分钟，移动次数剩余W次时，奶牛可以拿到的最大苹果数。 设置数组a[T]，记录T时间哪个位置有苹果。 状态转移方程： if(a[i]==1) { if(W与W0奇偶性相同，就可以拿苹果） dp[T,W]=max(dp[T-1,W]+1,dp[T-1,W+1]+1) //T-1时就在1位置，或者T-1时从2过来拿苹果 else dp[T,W]=max(dp[T-1,W],dp[T-1,W+1]) } if(a[i]==2) { 同理 }代码如下：
#include#include #include #include using namespace std;int dp[1001][31];int a[1001]; int main(){ int T,W,i,j; int ans=0,flag; memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a)); scanf("%d%d",&T,&W); if(W%2==0) flag=0; //flag=0，W为偶数，flag=1，W为奇数 else flag=1; for(i=1;i<=T;i++) scanf("%d",&a[i]); for(i=1;i<=T;i++) { for(j=W;j>=0;j--) { if(a[i]==1) //第一棵树有苹果 { if(j!=W) //边界，注意一下，小心越界了 { if(flag==1) { if(j%2==1) dp[i][j]=max(dp[i-1][j]+1,dp[i-1][j+1]+1); else dp[i][j]=max(dp[i-1][j],dp[i-1][j+1]); } else { if(j%2==0) dp[i][j]=max(dp[i-1][j]+1,dp[i-1][j+1]+1); else dp[i][j]=max(dp[i-1][j],dp[i-1][j+1]); } } else if(j==W) dp[i][j]=dp[i-1][j]+1; } else //第二棵树有苹果 { if(j!=W) { if(flag==1) { if(j%2==0) dp[i][j]=max(dp[i-1][j]+1,dp[i-1][j+1]+1); else dp[i][j]=max(dp[i-1][j],dp[i-1][j+1]); } else { if(j%2==1) dp[i][j]=max(dp[i-1][j]+1,dp[i-1][j+1]+1); else dp[i][j]=max(dp[i-1][j],dp[i-1][j+1]); } } } } } for(i=W;i>=0;i--) if(ans
一些测试样例：
7 2 2 1 1 2 2 1 1 6 7 3 2 1 1 2 2 1 1 6 7 4 2 1 1 2 2 1 1 7 8 4 2 2 1 1 2 1 2 1 7 8 1 2 2 2 1 1 2 1 2 5 8 2 2 2 2 1 1 2 1 2 6转载地址：http://sbdci.baihongyu.com/