挑战练习题2.3动态规划 poj2385Apple Catching dp

题目链接:

题意:

给你t，w 表示有t分钟掉苹果，你可以移动w次，求出在最大次数时最多能接到多少苹果。

题解:

dp[i][j] : 表示第i分钟跑了j次得到的最大值

代码:

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 typedef long long ll;
 5 #define MS(a) memset(a,0,sizeof(a))
 6 #define MP make_pair
 7 #define PB push_back
 8 const int INF = 0x3f3f3f3f;
 9 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
10 inline ll read(){
11     ll x=0,f=1;char ch=getchar();
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
13     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
14     return x*f;
15 }
16 //////////////////////////////////////////////////////////////////////////
17 const int maxn = 1e5+10;
18 
19 int a[maxn];
20 int dp[maxn][35];
21 
22 int main(){
23     int t,w;
24     cin >> t >> w;
25     for(int i=1; i<=t; i++)
26         cin >> a[i];
27 
28     //dp[i][j] : 表示第i分钟 跑了j次  得到的最大值
29 
30     if(a[1] == 1){
31         dp[1][0] = 1;
32         dp[1][1] = 0;
33     }else{
34         dp[1][0] = 0;
35         dp[1][1] = 1;
36     }
37 
38     for(int i=2; i<=t; i++){
39         for(int j=0; j<=w; j++){
40             if(j == 0)
41                 dp[i][j] = dp[i-1][j];
42             else
43                 dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]);
44             if(j%2+1 == a[i])
45                 dp[i][j]++;
46         }
47     }
48 
49     int ans = dp[t][0];
50     for(int i=1; i<=w; i++)
51         ans = max(ans,dp[t][i]);
52 
53     cout << ans << endl;
54 
55     return 0;
56 }