锐客网

  1. 首页 > 睿知 > it技术 > >

POJ-2385 Apple Catching---DP

IT知识applecatch

胸怀万里世界， 放眼无限未来。这篇文章主要讲述POJ-2385 Apple Catching---DP相关的知识，希望能为你提供帮助。
题目链接：
https://vjudge.net/problem/POJ-2385
题目大意：
两颗苹果树每一分会有树落下苹果，有人去接，但是来回两个树之间的次数是一定的，所以求出在最大次数时最多能接到多少苹果。
思路：
【POJ-2385 Apple Catching---DP】dp[i][j]表示在时间i，已经来回了j次时的最大苹果数目。
初始化dp[1][0]和dp[1][1]得根据第一个苹果是哪棵树落下的来进行初始化
转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-1])，并且如果在这个状态下，如果有苹果下落，得自加一
根据j的奇偶来判断在哪棵树下面，j为奇数在tree-2下面，j为偶数在tree-1下面

1 #include< iostream> 2 #include< vector> 3 #include< queue> 4 #include< algorithm> 5 #include< cstring> 6 #include< cstdio> 7 #include< set> 8 #include< map> 9 #include< cmath> 10 #include< sstream> 11 using namespace std; 12 typedef pair< int, int> Pair; 13 typedef long long ll; 14 const int INF = 0x3f3f3f3f; 15 int T, n, m, minans; 16 const int maxn = 1e3 + 10; 17 const int mod = 1e9; 18 int a[maxn]; 19 int dp[maxn][40]; //dp[i][j]表示前i分钟转移j次的最大苹果数目 20 int main() 21 { 22cin > > n > > m; 23for(int i = 1; i < = n; i++)cin > > a[i], a[i] %= 2; 24if(a[1] == 1)//初始状态 25{ 26dp[1][0] = 1; 27dp[1][1] = 0; 28} 29else 30{ 31dp[1][0] = 0; 32dp[1][1] = 1; 33} 34for(int i = 2; i < = n; i++) 35{ 36for(int j = 0; j < = m; j++) 37{ 38if(j == 0) 39//一次都没有转移,一直在tree1，如果此时a[i]为1，tree1掉苹果，可以加上，反之加上的也是0 40dp[i][j] = dp[i - 1][j] + a[i]; 41else 42{ 43dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]); 44 45//此时转移j次 46//j为奇数，在2下，若此时有苹果，则加一 47if((j % 2 == 1) & & (a[i] == 0)) 48dp[i][j]++; 49//j为偶数，在1下，若此时有苹果，则加一 50if((j % 2 == 0) & & (a[i] == 1)) 51dp[i][j]++; 52} 53} 54} 55int ans = 0; 56for(int i = 0; i < = m; i++)ans = max(ans, dp[n][i]); 57cout< < ans< < endl; 58return 0; 59 }

 

    推荐阅读


    上一篇：android布局控件

    下一篇：安卓ndk 忽略 error: undefined reference to &#39;找不到符号