Poj 1042 gone fishing-程序员宅基地

【题目大意】

题目就是在给定钓鱼时间，湖泊之间转移的时间，各湖泊初始鱼量，各湖泊鱼量的下降指数求在规定时间内的最大钓鱼量。

【解题思路】

本题目采用枚举+贪心的方法可以求解出来。首先我们需要对题目进行一些改造，我们需要枚举从第一个湖泊到第n个湖泊之间各种可能情况，然后再这些情况中选出最大值，输出结果。由于到各个湖泊的时间有所差异，我们首先需要把耽搁在转移路径上的时间除去，然后在剩余时间内确定钓鱼量的最大值，对于每次选择，我们采用贪心的方式选取最大值，进而得出最优解。

本题目需要特别注意输出格式，容易出现小错误：

我们需要考虑flag=0的情况，下面我们看一组数据：

*        看数据：
 *        2
 *        1
 *        0 0
 *        1 1
 *        1
 *        答案：
 *        60 0
 *        0
这里如果不写出代码：

          if(flag == 0)
          {
60             printf("%d", hour*5);
61             for(int i=1; i<n; i++)
62                 printf(", %d", 0);
63             printf("\nNumber of fish expected: %d\n\n", flag);
64  }
那么最后会一直wrong answer。

【AC代码】

#include<stdio.h>
struct lake
{
    int fish;
    int decrease;
    int time;
    int stay;
} K[30];
int main()
{
    int k_fish[30],k_stay[30],T[30];//T[i]表示路上花去时间
    int sum,maxn,flag,i,j,p,t,n,hour,k;
    while(scanf("%d",&n)&&n!=0)
    {
        //第一步的输入数据
        int hour;
        scanf("%d",&hour);
        hour*=12;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&K[i].fish);
            k_fish[i]=K[i].fish;//复制数组方便枚举各种情况时还原K[i].fish
        }
        for(int i=0;i<n;i++)
        scanf("%d",&K[i].decrease);
        K[0].time=0;
        for(int i=1;i<=n-1;i++)
        scanf("%d",&K[i].time);
       T[0]=K[0].time;
       flag=0;//初始化最大值
        for(int i=0;i<n;i++)
        {
            if(i)
            T[i]=T[i-1]+K[i].time;//在转移过程中所消耗的时间
            for(int s=0;s<n;s++)
            {K[s].fish=k_fish[s];K[s].stay=0;}//每一次枚举都初始化数据，并把在每一个lake的时间置为0
            sum=0;
            for(int h=1;h<=hour-T[i];h++)//在规定的时间内获取最大值
            {
                maxn=0;
                for(int k=0;k<=i;k++ )//寻找单位时间内最大的钓鱼量
                {
                    if(maxn<K[k].fish){maxn=K[k].fish;p=k;}
                }
                sum+=maxn;
                if(maxn>0)
                {
                    K[p].fish-=K[p].decrease;K[p].stay++;//在最大值的地方加上滞留时间，并把鱼量减小
                 }
                 else K[0].stay++;//如果没有找到，则在第一个湖那边加1；

            }
            if(sum>flag)
            {flag=sum;
             for(int j=0;j<=n;j++)
             k_stay[j]=K[j].stay*5;  //这里只对全部鱼量不全为0的情况，故下面在输出结果时要考虑flag是否为0
            }
        }
        if(flag == 0){
            printf("%d", hour*5);
            for(int i=1; i<n; i++)
                printf(", %d", 0);
            printf("\nNumber of fish expected: %d\n\n", flag);
        }
        else{
       for(j=0;j<n-1;j++)
            printf("%d, ",k_stay[j]);
            printf("%d\n",k_stay[n-1]);
       printf("Number of fish expected: %d\n\n",flag);//注意输出格式
    }
    }
    return 0;
}