网站站内交换链接怎么做/手机百度下载免费安装

传送门

题解：是个动态规划题，dp[i][j]是在第i分钟时已经走了j次所获得的最大苹果数量，所以到这一分钟可以推出来递推方程式为：

dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])，也就是在上一分钟时两棵树所能获得的最大值，刚开始都能想到这儿，一直考虑的是怎么判断出此时在哪棵树呢？最后仔细想想，既然走了j次已经知道了，刚开始又是在第1棵树那儿，所以就可以直接判出来了，这个有点无后效性的感觉了。

附上代码：

#include<iostream>
#include<cstdio>using namespace std;const int maxn=1e3+50;
const int maxw=35;int dp[maxn][maxw];
int a[maxn];int main()
{int t,w;scanf("%d%d",&t,&w);for(int i=1;i<=t;i++){scanf("%d",&a[i]);}if(a[1]==1){dp[1][0]=1;dp[1][1]=0;}else{dp[1][0]=0;dp[1][1]=1;}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;}else{dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);if((j+1)%2==0&&a[i]==2){dp[i][j]++;}else if((j+1)%2==1&&a[i]==1){dp[i][j]++;}}}}printf("%d\n",dp[t][w]);return 0;
}