poj 2385Apple Catching（简单dp）

浏览数：24 / 时间：2015年06月11日

 1 /*
 2     题意： 有两棵苹果树，每一棵苹果树每一秒间隔的掉落下来一个苹果，一个人在树下接住苹果，不让苹果掉落！
 3     人在两棵树之间的移动是很快的！但是这个人移动的次数是有限制的，问最多可以接住多少个苹果！
 4     
 5     思路：dp[i][j]表示的是前 i个苹果掉落之后， 移动次数是j的情况下的最多接住的苹果的个数！
 6     
 7     那么dp[i][j]=max(dp[i-1][j], dp[i][j-1]) + a[i]==j%2+1 ? 1 : 0;
 8     
 9     a[i]==j%2+1 表明第j次移动恰好移动到 第 a[i]棵苹果树下，此时这棵苹果树这号掉落下了苹果，正好接住！ 
10 */
11 #include<iostream>
12 #include<cstring>
13 #include<cstdio>
14 #include<algorithm>
15 #define M 1005
16 using namespace std;
17 
18 int dp[M][35];
19 
20 int n, m;
21 int a[M];
22 
23 int main(){
24    scanf("%d%d", &n, &m);
25    for(int i=1; i<=n; ++i)
26       scanf("%d", &a[i]);
27    if(a[1]==1) dp[1][0]+=1;
28    for(int i=2; i<=n; ++i){
29        dp[i][0]=dp[i-1][0];
30        if(a[i]==1)
31           dp[i][0]+=1;
32    }
33       
34    for(int j=1; j<=m; ++j)
35       for(int i=j; i<=n; ++i){
36              dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
37            int cc=j%2+1;
38            if(a[i]==cc)
39               dp[i][j]+=1;
40       } 
41    printf("%d\n", dp[n][m]);
42    return 0;
43 }