poj 2385 Apple Catching(记录结果再利用的动态规划)

古人已用三冬足，年少今开万卷余。这篇文章主要讲述poj 2385 Apple Catching(记录结果再利用的动态规划)相关的知识，希望能为你提供帮助。
传送门
https://www.cnblogs.com/violet-acmer/p/9852294.html

题意：
有两颗苹果树，在每一时刻只有其中一棵苹果树会掉苹果，而Bessie可以在很短的时间内在两个苹果树间切换，但每一时刻只能切换一下；
求在1~T时刻，Bessie在最多可以切换W次的前提下最多可以获得多少苹果？
题解：
定义变量dp[ i ][ j ] : 前 i 时刻，移动 j 步所获得的最大的苹果数量；
据此写出状态转移方程：

文章图片

如何判断在i处是否的到苹果呢？
①如果dp[i-1][ j-1]为偶数，那么在 i 处移动之前，Bessie应该在 2 号苹果树下，因为在 i 处移动了，Bessie是在 1 号苹果树下等待 i 时刻的苹果
反之，Bessie是在 2 号苹果树下等待 i 时刻的苹果。
②如果dp[i-1][ j ]为偶数，且Bessie在 i 时刻并没有移动，所以Bessie是在 2 号苹果树下等待 i 时刻的苹果
反之，Bessie是在 1 号苹果树下等待 i 时刻的苹果。
poj维护中............之前交的代码本地没保存，现在不想写了，明天看看poj还能登陆吗。。。。。啊啊啊啊
AC代码：

文章图片

1 #include< iostream> 2 #include< cstdio> 3 #include< cstring> 4 #include< algorithm> 5 using namespace std; 6 #define mem(a,b) memset(a,b,sizeof(a)) 7 const int maxn=1e3+10; 8 9 int T,W; 10 int tree[maxn]; //tree[i]=1/2 : i时刻果树1/2掉苹果 11 int dp[maxn][40]; 12 13 int inOne(int i){//判断i时刻果树1是否掉苹果 14return tree[i] == 1 ? 1:0; 15 } 16 int inTwo(int i){//判断i时刻果树2是否掉苹果 17return tree[i] == 2 ? 1:0; 18 } 19 int walk(int i,int j)//在i时刻移动 20 { 21if((j-1)& 1) 22return dp[i-1][j-1]+inOne(i); 23return dp[i-1][j-1]+inTwo(i); 24 } 25 int noWalk(int i,int j)//在i时刻不移动 26 { 27if(j& 1) 28return dp[i-1][j]+inTwo(i); 29return dp[i-1][j]+inOne(i); 30 } 31 void Solve() 32 { 33mem(dp,0); 34for(int i=1; i < = T; ++i)//i时刻 35for(int j=0; j < = W; ++j)//前i时刻共移动j步 36if(j == 0) 37dp[i][j]=dp[i-1][j]+inOne(i); 38else 39dp[i][j]=max(walk(i,j),noWalk(i,j)); 40printf("%d\\n",*max_element(dp[T]+0,dp[T]+W+1)); 41 } 42 int main() 43 { 44scanf("%d%d",& T,& W); 45for(int i=1; i < = T; ++i) 46scanf("%d",tree+i); 47Solve(); 48 }

View Code【poj 2385 Apple Catching(记录结果再利用的动态规划)】