首页 > 代码库 > poj 2385 Apple Catching
poj 2385 Apple Catching
题目大意：有两棵苹果树，编号为1，2，每分钟有一棵树会掉落一个苹果。一头牛在树下接苹果，每分钟只能站在一棵树下，但在树间转移的时间忽略不计。给定最大的转移次数w，问这只牛最多能接住多少苹果?
分析：这道题用动态规划求解，关键问题是状态是什么？
不妨按时间来思考，一给定时刻i，转移次数已知为j, 则它只能由两个状态转移而来。
即上一时刻同一棵树或上一时刻不同的树
则这一时刻在转移次数为j的情况下最多能接到的苹果为那两个状态的最大值再加上当前能接受到的苹果。（注意当前能否拿到苹果只与转移次数有关）
即
1 dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]);2 if(j%2+1 == i) {3 dp[i][j]++;4 }
在0时刻，不管移动次数为几，接受的苹果都为0
本题代码如下
1 /*dp[t][w] 2 3 dp[0][0..w] = 0; 4 dp[i][0] = dp[i-1][0]; 5 dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]); 6 if(j%2+1 == i) { 7 dp[i][j]++; 8 }*/ 9 #include <cstdio>10 #include <cstring>11 #include <iostream>12 using namespace std;13 int dp[1002][35];14 int apple[1002];15 16 int main(int argc, char const *argv[])17 {18 int t, w;19 scanf("%d %d",&t,&w);20 for(int i = 1; i <= t; i++) {21 scanf("%d",&apple[i]);22 }23 memset(dp, 0, sizeof(dp));24 for(int i = 1; i <= t; i++) {25 for(int j = 0; j <= w; j++) {26 if(j == 0) {27 dp[i][j] = dp[i-1][j];28 }29 else {30 dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]);31 }32 if(j%2 + 1 == apple[i]) {33 dp[i][j]++;34 }35 }36 }37 int ans = dp[t][0];38 for(int j = 1; j <= w; j++) {39 if(ans < dp[t][j]) {40 ans = dp[t][j];41 }42 }43 printf("%d\n",ans);44 45 46 return 0;47 }
动态规划确实不容易啊！
poj 2385 Apple Catching
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。