POJ - 2385 捡苹果(简单DP)

xiaoxiao2021-03-01  5

题目大意:有两颗苹果树,会一起掉苹果,某一秒一个人只能在一棵树下,移动次数有限,怎么移动可以捡取到更多的苹果(默认在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; } }

 

转载请注明原文地址: https://www.6miu.com/read-3850358.html

最新回复(0)