`
阿尔萨斯
  • 浏览: 4108300 次
社区版块
存档分类
最新评论

POJ 1042 Gone Fishing(贪心+枚举)

 
阅读更多

POJ 1042 Gone Fishing(贪心+枚举)

http://poj.org/problem?id=1042

题意:

John现有h个小时的空闲时间,他打算去钓鱼。钓鱼的地方共有n个湖,所有的湖沿着一条单向路顺序排列(John每在一个湖钓完鱼后,他只能走到下一个湖继续钓),John必须从1号湖开始钓起,但是他可以在任何一个湖结束他此次钓鱼的行程。

此题以5分钟作为单位时间,John在每个湖中每5分钟钓的鱼数随时间的增长而线性递减。每个湖中头5分钟可以钓到的鱼数用fi表示,每个湖中相邻5分钟钓鱼数的减少量用di表示,John从任意一个湖走到它下一个湖的时间用ti表示。

求一种方案,使得John在有限的h小时中可以钓到尽可能多的鱼。输出具体在第i个湖花了多少时间,如果存在多个最优解,输出优先第1个,第2个..湖中花时间最多的解.

分析:

首先我们可以肯定John钓鱼的时候如果从i走到了j号鱼塘肯定就不会回去了,否则浪费时间回头.(想想是不是) 所以John钓鱼花在走路的时间肯定是从i到i+1湖的时间.

由于总时间= 钓鱼时间+走路时间. 所以我们枚举John最后钓鱼的湖是第i个,然后我们算出他一共花了多少时间走路,那么剩下的就是钓鱼花的时间.

假设剩下x单位的钓鱼时间,且我们钓鱼在[1,i]号湖范围内钓,所以每单位时间选取当前可钓鱼数目最多的湖钓鱼. 最终我们能得到钓鱼最大数目.(虽然钓鱼顺序不是这样的,但是我们能通过合理的安排钓鱼顺序来达到这个解.即该解可行)

最终我们只需要对比我们枚举不同的终结湖位置所得到的解,就可以得到最优解.

注意:

对于初始能钓鱼的数目就全为0的情况(fi[i]数组全0),输出要注意.

如果fi-d<0之后fi应该变成0.

优先选择序号小的湖钓鱼.

最终我本来第一次交的代码就是对的,结果本题有个BUG,导致我无限超时,真是悲剧.最后通过不断的修改代码,找到了这个BUG,这应该是POJ的问题.代码41行指出了那个BUG.这不是我第一次发现POJ诡异BUG

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=30;

int n,h;        //n表湖数目,h表单位时间 数目
int t[maxn];    //t[i]表从i湖走到i+1湖花的单位时间
int f[maxn];    //初始每单位时间能钓的鱼量
int d[maxn];    //每单位时间钓鱼量的减少量
int cf[maxn];   //当前每单位时间能钓的鱼量

int ans;        //总钓鱼量
int sum[maxn];  //每个湖对应的钓鱼时间

void get_max(int k,int &ans,int *sum)//选[1,k]内的湖,获得当前单位时间的钓鱼量,并更新对应数组
{
    int max_v=-1,id=-1;
    for(int i=1;i<=k;i++)//从前往后选,保证解不唯一时也符合要求
    if(cf[i]> max_v)
    {
        max_v=cf[i];
        id=i;
    }
    ans += cf[id];
    sum[id]++;
    cf[id] -=d[id];
    if(cf[id]<0) cf[id] = 0;
}
void solve()
{
    for(int i=1;i<=n;i++)   //枚举最后一个钓鱼的湖
    {
        int fish_time = h;  //仅用于钓鱼的时间
        for(int j=1;j<i;j++)
            fish_time = fish_time - t[j];

        int temp_ans=0;//当前解
        int temp_sum[maxn]={0};//当前解
        memcpy(cf,f,sizeof(f));

        for(int j=0;j<fish_time;j++)//神BUG,若此句改为 while(fish_time--) 则无限超时.原因不明
        {
            get_max(i,temp_ans,temp_sum);
        }

        if(temp_ans > ans)//当前解更优
        {
            ans=temp_ans;
            memcpy(sum,temp_sum,sizeof(sum));
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(i>1) printf(", ");
        printf("%d",sum[i]*5);
    }
    printf("\nNumber of fish expected: %d\n\n",ans);
}

int main()
{
    while(scanf("%d",&n)==1&&n)
    {
        scanf("%d",&h);
        h= h*12;
        ans = 0;
        memset(sum,0,sizeof(sum));
        sum[1]= h;//默认当所有f=0时的解
        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]);
        solve();
    }
    return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics