首页 > 代码库 > poj 2385 Apple Catching dp

poj 2385 Apple Catching dp

http://poj.org/problem?id=2385


题意:有两棵苹果树,每分钟都会有一棵树上会掉下来一个苹果,你必须要站在这棵树下才能接到这棵树掉下来的苹果,你可以在两棵树之间来回走动,而且不花费时间,但是来回走的次数不超过w次,现在告诉你每分钟从哪棵树上会掉下来苹果,问你最多能接着多少个,你的其实位置实在第一棵树下。

思路:用dp[i][j][k]表示第i分钟,已经来回走了j次,而且现在在第k棵树下(k=0表示在第一棵树下,k=1表示在第二棵树下),能接到的最多的苹果数量,那么如果第i分钟,是第一课树掉下苹果,那么容易想到dp[i]][j][0]=max(dp[i-1][j][0]+1,dp[i-1][j-1][1]+1),因为可能之前就在第一棵树下,那么就不需要走动,就可以再接一个苹果,或者之前在第二棵树下,那么就要移动一次才能到第一棵树下,再接一个苹果;dp[i][j][1]=dp[i-1][j][1],以为根据贪心的思想,不可能知道第一棵树要落下苹果,还从第一棵树下走到第二棵树下,所以k=1的情况只有由dp[i-1][j][1]推出。那么同理,我们可以得到第i分钟,是第二棵树掉下苹果的情况了,这里就不再叙述了。如果不明白,就看下面的代码好了。需要注意的是,最后的答案不一定是移动了最大次数的情况,比如全部都是第一棵苹果树在掉苹果,那么不用移动就可以接到最多的苹果,所以,必须要要在所有的情况中找最大值。


#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

int dp[1010][35][2];
int a[1010];

int main()
{
    int n,m;
    while(cin>>n>>m){
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++) if(j<=i){
                if(a[i]==1){
                    if(j)
                        dp[i][j][0]=max(dp[i-1][j][0]+1,dp[i-1][j-1][1]+1);
                    else dp[i][j][0]=dp[i-1][j][0]+1;
                    dp[i][j][1]=dp[i-1][j][1];
                }
                else{
                    dp[i][j][0]=dp[i-1][j][0];
                    if(j)
                        dp[i][j][1]=max(dp[i-1][j][1]+1,dp[i-1][j-1][0]+1);
                    else dp[i][j][1]=dp[i-1][j][1]+1;
                }
            }
        }
        int ans=0;
        for(int i=0;i<=m;i++){
            ans=max(ans,dp[n][i][0]);
            ans=max(ans,dp[n][i][1]);
        }
        cout<<ans<<endl;
    }
    return 0;
}





poj 2385 Apple Catching dp