poj2385 很好的动态规划

青旅半醒 2022-08-03 05:14 173阅读 0赞

以前做的

/* poj2385 dp[i][j]表示第i分钟移动j次最多苹果数
    *  注意初始化不移动时候 呆在第一棵树下能吃到的苹果数
    *  第一分钟可以移动到第二颗树下吃苹果
    *  j的值的奇偶性能判断牛的位置
    *  能吃到的话可能从另一棵树来，也可能是本身就在这棵树下
    *  不能吃到的话一定是本身就在这棵树下（等他后面掉呢）
    *  不能吃到的话还用从另一棵树过来？
    *  最后找小于等于w步数中dp数组的最大值 题目是小于等于w步中吃到最多的。
    */
    
    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    inline int max(int a,int b)
    {
        return a>b?a:b;
    }
    int a[1001];
    int dp[1002][31];
    int main()
    {
        int t,w;
        while(~scanf("%d%d",&t,&w))
        {
    
            for(int i=0;i<t;i++)cin>>a[i];
            memset(dp,0,sizeof(dp));
            dp[0][0]=(a[0]==1)?1:0;
            dp[0][1]=(a[0]==2)?1:0;
            for(int i=1;i<t;i++){
                dp[i][0] = dp[i-1][0]+2-a[i];//不移动呆在第一棵树下 能吃到的苹果数
                for(int j=1;j<=w && j<=i ;j++){
                    if((j%2==1 && a[i]==2) || (j%2==0 && a[i]==1)){//牛移动奇数步并且第1棵树掉苹果，牛移动偶数步且第二颗树掉苹果
                        dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+1;//从另一棵树过来或者本身就在这棵树下 能吃到所以加一
                    }
                    else {
                        dp[i][j]=dp[i-1][j];//吃不到苹果 吃不到苹果就不用从另一棵树下移动过来了~·~移动过来又吃不到来干嘛？
                    }
                }
            }
            int ans=-1000;
            for(int i=0;i<=w;i++){//判断小于等于w步中最大的苹果数 题目中是最多w步
                ans=max(ans,dp[t-1][i]);
            }
            cout<<ans<<endl;
    
        }
        return 0;
    }

现在做的：

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    int dp[1006][36];
    int a[1006];
    int main()
    {
        int T,W;
        while(~scanf("%d%d",&T,&W))
        {
            for(int i=1;i<=T;i++)
            {
                a[i]=in();
            }
            dp[1][0]=2-a[1];
            dp[1][1]=a[1]-1;
            for(int i=2;i<=T;i++)
            {
                dp[i][0]=dp[i-1][0]+2-a[i];
            }
            for(int i=2;i<=T;i++)
            {
                for(int j=1;j<=W;j++)
                {
                    if(j & 1)//在第二课树下
                    {
                        if(a[i]==2)dp[i][j]=dp[i-1][j]+1;
                        else dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j]);
                    }
                    else
                    {
                        if(a[i]==2) dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j]);
                        else dp[i][j]=dp[i-1][j]+1;
                    }
                }
            }
            int ans=-inf;
            for(int i=1;i<=W;i++)
            {
                ans=max(ans,dp[T][i]);
            }
            printf("%d\n",ans);
        }
        return 0;
    }