题目链接：http://poj.org/problem?id=2385
题意：最开始Bessie站在树1下面，每一个单位时间有颗苹果从树1或者树2上落下来。每个单位时间Bessie可以移动一次位置，时间长度为T(<=1000)，Bessie最多移动W次(<=30)。求Bessie最多能得到多少苹果。
思路：好久没写过dp题了，这道题又弄了好久。QAQ...
创建dp[1005][35]。
其中dp[i][j]表示第i个单位时间时，Bessie移动了j次最多能得到的苹果数。首先要初始化i=1的情况：
if(a[1]==1) dp[1][0]=1; else dp[1][1]=1;
当i>=2时：
如果j==0：dp[i][j]=dp[i-1][j]+(a[i]==1)
否则：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1)
if(j%2+1==a[i]) ++dp[i][j]。
代码如下：
#include<cstdio> #include<algorithm> using namespace std; int t,w,ans,a[1005],dp[1005][35]; int main(){ scanf("%d%d",&t,&w); for(int i=1;i<=t;++i) scanf("%d",&a[i]); if(a[1]==1) dp[1][0]=1; else dp[1][1]=1; for(int i=2;i<=t;++i){ for(int j=0;j<=min(i,w);++j){ if(j==0) dp[i][j]=dp[i-1][j]+(a[i]==1); else{ dp[i][j]=max(dp[i-1][j-1],dp[i-1][j]); if(j%2+1==a[i]) ++dp[i][j]; } } } for(int i=0;i<=min(t,w);++i) if(dp[t][i]>ans) ans=dp[t][i]; printf("%d\n",ans); return 0; }
转载于:https://www.cnblogs.com/FrankChen831X/p/11180020.html
