POJ-2385

xiaoxiao2021-02-28  8

题目大意:

有两棵苹果树(编号1和2),每分钟其中一棵树将会落下一个苹果,而牛要在两棵树下来回跑去接掉下的苹果(因为它不吃掉在地下的苹果)。而这只牛很懒,它不会为了吃而不停地来回跑。这里假设在t分钟内,牛只愿意跑w次,问牛最多能吃几个苹果。默认牛最初在1号树下。

我的理解:

这是一个DP问题。首先应根据第一分钟的苹果落下情况,对tree数组赋初值。

DP状态方程 dp[i][j] = max( dp[i-1][j] + dp[i-1][j-1] ),意思就是在前i分钟来回跑了j次吃到的苹果的最大数目;

其中dp[i-1][j]代表着上一次没有移动,dp[i-1][j-1] 代表上一次移动了。

其中还要注意的是当此次移动刚好有苹果落下时要将dp[]i[j]++;

我的代码:

#include <iostream> #include <cstdio> #include <cstring> #define MAX_T 1005 #define MAX_W 50 using namespace std; int dp[MAX_T][MAX_W]; int t,w; int tree[MAX_T]; int main() { freopen("D:/OJ/挑战程序设计竞赛/CatchApple.txt","r",stdin); int ans; while(scanf("%d %d",&t,&w) != EOF){ memset(dp,0,sizeof(dp)); //cin>>t>>w; for(int i = 1;i<=t;i++){ cin>>tree[i]; } if(tree[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]+tree[i]%2; continue; } dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]); if(j%2+1 == tree[i]){ dp[i][j]++; } } } } ans = dp[t][0]; for(int i = 0;i<=w;i++){ if(ans < dp[t][i]){ ans = dp[t][i]; } } cout<<ans<<endl; return 0; }

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

最新回复(0)