poj2385_dp经典

题目链接：http://poj.org/problem?id=2385

题目大意：题意很简单，两颗苹果树每一分钟会有树会落下苹果，Farmer John去接，但是来回两个树之间的次数是一定的，所以求出在最大次数时最多能接到多少苹果。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <set>
 8 #include <map>
 9 #include <vector>
10 using namespace std;
11 
12 int dp[1010][50], a[1010];
13 int main()
14 {
15     int t, w, i, j;
16     while(~scanf("%d %d", &t, &w))
17     {
18         for(i = 1; i <= t; i++)
19             scanf("%d", a + i);
20         memset(dp, 0, sizeof(dp));
21         if(a[1] == 1)
22         {
23             dp[1][0] = 1;
24             dp[1][1] = 0;
25         }
26         else
27         {
28             dp[1][0] = 0;
29             dp[1][1] = 1;
30         }
31         for(i = 2; i <= t; i++)
32         {
33             for(j = 0; j <= w; j++)
34             {
35                 if(j == 0)
36                 {
37                     dp[i][j] = dp[i - 1][j] + a[i] % 2;
38                     continue;
39                 }
40                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
41                 if(j % 2 + 1 == a[i])
42                     dp[i][j]++;
43             }
44         }
45         printf("%d
", dp[t][w]);
46     }
47     return 0;
48 }