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[30],f[30],d[30];
int ans1[30][30],ans2[30];

int main(){
    while(scanf("%d",&n),n){
        for(int i=1;i<=n;++i){
            ans2[i]=0;
            for(int j=1;j<=n;++j)
                ans1[i][j]=0;
        }
        scanf("%d",&h);
        h*=12;
        for(int i=1;i<=n;++i)
            scanf("%d",&f[i]);
        for(int i=1;i<=n;++i)
            scanf("%d",&d[i]);
        for(int i=1;i<=n-1;++i)
            scanf("%d",&t[i]);
        for(int i=1;i<=n;++i){
            int nw[30],hh=h;
            for(int j=1;j<=i;++j){
                nw[j]=f[j];
                if(j<i) hh-=t[j];
            }
            if(hh<=0) break;
            while(hh--){
                int Max=nw[1],k=1;
                for(int j=2;j<=i;++j)
                    if(nw[j]>Max){
                        Max=nw[j];
                        k=j;
                    }
                nw[k]-=d[k];
                if(nw[k]<0) nw[k]=0;
                ans2[i]+=Max;
                ++ans1[i][k];
            }
        }
        int k=1,Max=ans2[k];
        for(int i=2;i<=n;++i)
            if(ans2[i]>Max)
                k=i,Max=ans2[i];
        for(int i=1;i<=n;++i){
            if(i!=1) printf(", ");
            printf("%d",ans1[k][i]*5);
        }
        printf("
");
        printf("Number of fish expected: %d

",ans2[k]);
    }
    return 0;
}