POJ - 2385 Apple Catching（动态规划）

本文主要是介绍POJ - 2385 Apple Catching（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接

初学DP，虽然都是简单的DP，但每做出一道题都不容易啊，不能仅仅局限于一题，更重要的是要触类旁通。

dp[i+1][j] = max(dp[i][j], dp[i][j-1]) + ( t==(j%2+1) ? 1:0);

表示前i个苹果，走j次的最大获得值。可以压缩空间用一维数组即可。

其中( t==(j%2+1) ? 1:0)表示：若已停留在该树，则+1；

#include <iostream>
#include <cstdio>
using namespace std;
const int MAX_T = 1001, MAX_W = 31;
int T, W;
int dp[MAX_W];
inline int cnt(int t, int j) { return t == (j%2+1) ? 1 : 0;}int main()
{//freopen("in.txt", "r", stdin);scanf("%d%d", &T, &W);for(int i = 0; i < T; i++){int t;scanf("%d", &t);for(int j = W; j >= 0; j--)if(j == 0)dp[j] += cnt(t, j);elsedp[j] = max(dp[j-1], dp[j]) + cnt(t, j);}int Max = -1;for(int j = 0; j <= W; j++) Max = max(Max, dp[j]);printf("%d\n", Max);return 0;
}

这篇关于POJ - 2385 Apple Catching（动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---