poj1042（贪心+枚举）

题目链接：https://vjudge.net/problem/POJ-1042

题意：给n个湖，给出每个湖第一次打捞时鱼的数量f[i]，每单位时间鱼减少的数量d[i]，从湖i到湖i+1用时t[i]，在12×h个单位时间内，求最多能获得多少鱼。在获得鱼数量相同的情况下，选择在湖1呆时间最长的方案，若在湖1呆的时间一样，则选呆在湖2时间最长的方案...输出在每个湖呆的时间和最多获得鱼的数量。

思路：最近3天学校开运动会，下周要去西安邀请赛了，所以最近开始通过刷题复习学过的算法。今天状态真的不怎么好，昨晚睡得不好，上午11点多开了这道题，最开始从DP角度想，想好久也没有头绪，看了网上大部分用贪心写的，也有用dp的，今天累，不想研究dp的思路。。。就用贪心来写把。因为各种原因这题写了一下午，各种找bug，心态爆炸，也不知道是因为状态不好还是题目坑QAQ...

　　好吧，回到题目上来。贪心思路很简单，也很巧妙。枚举最多到达湖i，然后用时间h减去中间行走的时间，剩下的时间就是花在钓鱼上的时间啦。不用考虑行走的时间，这时候由贪心策略，每次找当前能钓到最多鱼的湖去钓，而不一定是后面的湖，这里稍微想一想，不难理解。

　　再说一下我在写这题时遇到的问题吧QAQ。最开始提交是TLE，我懵逼了。。这数据！这复杂度怎么会T，找好久发现while循环那出现了死循环，因为hh可能<0，这个时候要break。然后就是一直WA，WA了十多发，WA哭。。原因是这组数据：

　　0 0

　　1 1

　　答案是0,但我最终找k时，应该将k初始化为1,再找，不然k是随机的。。累。。

AC代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int n,h;

int t[],f[],d[];

int ans1[][],ans2[];

int main(){

    while(scanf("%d",&n),n){

        for(int i=;i<=n;++i){

            ans2[i]=;

            for(int j=;j<=n;++j)

                ans1[i][j]=;

        }

        scanf("%d",&h);

        h*=;

        for(int i=;i<=n;++i)

            scanf("%d",&f[i]);

        for(int i=;i<=n;++i)

            scanf("%d",&d[i]);

        for(int i=;i<=n-;++i)

            scanf("%d",&t[i]);

        for(int i=;i<=n;++i){

            int nw[],hh=h;

            for(int j=;j<=i;++j){

                nw[j]=f[j];

                if(j<i) hh-=t[j];

            }

            if(hh<=) break;

            while(hh--){

                int Max=nw[],k=;

                for(int j=;j<=i;++j)

                    if(nw[j]>Max){

                        Max=nw[j];

                        k=j;

                    }

                nw[k]-=d[k];

                if(nw[k]<) nw[k]=;

                ans2[i]+=Max;

                ++ans1[i][k];

            }

        }

        int k=,Max=ans2[k];

        for(int i=;i<=n;++i)

            if(ans2[i]>Max)

                k=i,Max=ans2[i];

        for(int i=;i<=n;++i){

            if(i!=) printf(", ");

            printf("%d",ans1[k][i]*);

        }

        printf("\n");

        printf("Number of fish expected: %d\n\n",ans2[k]);

    }

    return ;

}

巴特西

poj1042（贪心+枚举）

最新文章

热门文章