C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

poj 1042 Gone Fishing(贪心+枚举)

Posted on 2012-04-06 08:13 C小加 阅读(1828) 评论(3)  编辑 收藏 引用 所属分类: 解题报告

第一次WA,发现输出格式不对,改掉。

第二次WA,对结果相等的情况没有考虑,改掉。

第三次AC

题意和题解见黑书P13

需要注意的是要枚举从第一个湖走到最后一个湖的每一种情况,对结果相等这种情况做特殊处理。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXM=30;
int n,h;
int f[MAXM],d[MAXM],t[MAXM];
int each_time[MAXM];
int ans_time[MAXM];
int tf[MAXM];
int ans;
//初始化
void init()
{
    memset(each_time,0,sizeof(each_time));
    memset(ans_time,0,sizeof(ans_time));
    ans=0;
}
//输入
bool input()
{
    init();
    scanf("%d",&n);
    if(0==n) return false;
    scanf("%d",&h);
    for(int i=0;i<n;++i)
    {
        scanf("%d",f+i);
    }
    for(int i=0;i<n;++i)
    {
        scanf("%d",d+i);
    }
    for(int i=0;i<n-1;++i)
    {
        scanf("%d",t+i);
    }
    return true;
}

void solve(int rem_time,int q)
{
    int tans=0;
    memset(each_time,0,sizeof(each_time));

    memcpy(tf,f,sizeof(f));
    for(int i=0;i<rem_time;++i)//找鱼的数量最多的湖
        {
            int pos=0,max_fish=tf[0];
            if(q>0)
            for(int j=1;j<=q;++j)
            {
                if(max_fish<tf[j])
                {
                    max_fish=tf[j];
                    pos=j;
                }
            }
            ++each_time[pos];
            tans+=tf[pos];
            tf[pos]-=d[pos];
            if(tf[pos]<0) tf[pos]=0;

        }
        if(tans>ans)
        {
            ans=tans;
            memcpy(ans_time,each_time,sizeof(each_time));
        }
        else if(tans==ans)//细节,答案相等时做的处理。
        {
            int i;
            for(i=0;i<n;++i)
            {
                if(each_time[i]!=ans_time[i]) break;
            }
            if(each_time[i]>ans_time[i])
            {
                memcpy(ans_time,each_time,sizeof(each_time));
            }
        }
}

void print()
{
    printf("%d",ans_time[0]*5);
    for(int i=1;i<n;i++)
    {
        printf(", %d",ans_time[i]*5);
    }
    printf("\nNumber of fish expected: %d\n\n",ans);
}
int main()
{
   // freopen("in.txt","r",stdin);
   
// freopen("out2.txt","w",stdout);
    while(input())
    {
        int rem_time=h*60;
        rem_time/=5;
        solve(rem_time,0);
        for(int i=0;i<n-1;++i)//枚举每个湖
        {
            rem_time-=t[i];
            solve(rem_time,i+1);
        }
        print();

    }

    return 0;
}

Feedback

# re: poj 1042 Gone Fishing(贪心+枚举)  回复  更多评论   

2012-04-09 17:32 by coreBugZJ
曾经ACM的路过。。。

# re: poj 1042 Gone Fishing(贪心+枚举)  回复  更多评论   

2012-04-10 08:36 by C小加
我也快结束ACM生涯了@coreBugZJ

# re: poj 1042 Gone Fishing(贪心+枚举)  回复  更多评论   

2012-04-19 17:07 by SunRise_at
我已经结束了啊。。。@C小加

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理