挑战程序设计竞赛第二章、动态规划部分

POJ2385

题意：有两棵树，初始时第一棵树会掉苹果，一头牛初时在第一颗树下，一共有T秒，牛最多走W步，给出树掉果子的序列，求牛该怎么走才能最大化收益

题解：递推方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])，其中dp[i][j]表示第i秒还能走j步时能拿到的最大价钱。

 1 #pragma GCC optimize(3)
 2 #include <stdio.h>
 3 #include <time.h>
 4 #include <algorithm>
 5 #include <bitset>
 6 #include <cctype>
 7 #include <cmath>
 8 #include <cstdio>
 9 #include <cstdlib>
10 #include <cstring>
11 #include <deque>
12 #include <functional>
13 #include <iostream>
14 #include <map>
15 #include <queue>
16 #include <set>
17 #include <sstream>
18 #include <stack>
19 #include <string>
20 #include <utility>
21 #include <vector>
22 using namespace std;
23 const double EPS = 1e-9;
24 const int INF = 2147483647;
25 const long long LLINF = 9223372036854775807;
26 const double PI = acos(-1.0);
27 
28 inline int READ() {
29     char ch;
30     while ((ch = getchar()) < 48 || 57 < ch)
31         ;
32     int ans = ch - 48;
33     while (48 <= (ch = getchar()) && ch <= 57)
34         ans = (ans << 3) + (ans << 1) + ch - 48;
35     return ans;
36 }
37 
38 #define REP(i, a, b) for (int i = (a); i <= (b); i++)
39 #define PER(i, a, b) for (int i = (a); i >= (b); i--)
40 #define FOREACH(i, t) for (typeof(t.begin()) i = t.begin(); i != t.end(); i++)
41 #define MP(x, y) make_pair(x, y)
42 #define PB(x) push_back(x)
43 #define SET(a) memset(a, -1, sizeof(a))
44 #define CLR(a) memset(a, 0, sizeof(a))
45 #define MEM(a, x) memset(a, x, sizeof(a))
46 #define ALL(x) begin(x), end(x)
47 #define LL long long
48 #define Lson (index * 2)
49 #define Rson (index * 2 + 1)
50 #define pii pair<int, int>
51 #define pll pair<LL, LL>
52 #define MOD ((int)1000000007)
53 #define MAXN 1000 + 5
54 ///**********************************START*********************************///
55 
56 int T, W;
57 int dp[MAXN][30 + 5];  //当前为第i秒还能走j步时能拿到的最大价钱。
58 int order[MAXN];
59 
60 int main() {
61     freopen("input.txt", "r", stdin);
62     T = READ(), W = READ();
63     CLR(dp);
64     SET(order);
65     REP(i, 1, T) order[i] += READ();
66 
67     int st = 0;
68     REP(i, 1, T) REP(j, 0, W) {
69         dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]);
70         if (j % 2 == order[i]) dp[i][j]++;
71     }
72 
73     int ans = -1;
74     REP(j, 1, W) ans = max(ans, dp[T][j]);
75     cout << dp[T][W] << endl;
76     return 0;
77 }