pku1042 Gone Fishing (贪心好题)

题目：

题目大意是说在笔直的路边有一些池塘，从左到右编号为1,2...n。John共有H个小时的空余时间，他希望能钓到尽量多的鱼。他从池塘1出发，向右走，有选择的在一些池塘边停留一定的时间钓鱼，现已经测出John从第i个湖到第i+1个湖走路需要的时间5*Ti分钟，还测出在第i个湖边停留，第一个5分钟可以钓到的鱼Fi，以后每5分钟能钓到的鱼的数量减少Di.为简化问题假定没有其它因素会影响到他钓鱼的数量，要求出John能钓到最多鱼的方案。

这题的主要分析思想来自lrj书的13页。主要思路如下：

把钓5分钟鱼称为钓一次鱼。首先枚举John需要走过的池塘的数目X，即假设他从湖泊1走到湖泊X,则路上花去的时间T=sum(Ti) i=1...X-1.在这个前提下，可以认为John能从一个池塘"瞬间转移"到另一个池塘，即在任意一个时刻都可以从湖泊1到湖泊X中任选一个钓一次鱼(很重要)。现在采用贪心策略，每次选择鱼最多的湖泊钓一次鱼。对于每个池塘来说，由于在任何时候鱼的数目只和John在该池塘里钓鱼的次数有关，和钓鱼的总次数无关，所以这个策略是最优的。假设一共允许钓k次鱼，那么每次在N个池塘中选择鱼最多的一个钓。总的时间复杂度为O(kn^2)。

这题xsy是用DP做的。我是按书上的思路用贪心解决，我比他的快100MS左右。

my code:

 

include<iostream>
using namespace std;

const int size=26;
int n,h,ca;
int f[size],t[size],d[size],tf[size];
int ans[size],tans[size],flag;

int main()
{
    int i,j,k,sum,time,tt,tnum,maxsum,nextmin,t1;
    while(cin>>n)
    {
        if(n==0)break;ca++;
        if(ca>1)cout<<endl;
        cin>>h;maxsum=-100;h*=60;t1=0;

        for(i=1;i<=n;i++) {cin>>f[i];tf[i]=f[i];}
        for(i=1;i<=n;i++) cin>>d[i];
        for(i=1;i< n;i++) cin>>t[i];
        for(i=1;i<=n;i++) ans[i]=tans[i]=0;

        for(i=1;i<=n;i++)
        {
            t1+=t[i-1];
            time=(h-t1*5)/5;sum=0;
            for(j=1;j<=i;j++) tans[j]=0;
            if(i==1&&d[1]!=0)
            {
                tans[1]=time;
                tt=f[1]/d[1];
                if(f[1]%d[1]) tt++;
                if(time>=tt) sum=(f[1]+f[1]-(tt-1)*d[1])*tt/2;
                else sum=(f[1]+f[1]-(time-1)*d[1])*time/2;
                time=0;
            }
            else if(i==1&&d[1]==0)
            {
                tans[1]=time;
                sum=time*f[1];
                time=0;
            }
            while(time>0)
            {
                tnum=0;k=1;nextmin=0;flag=0;
                for(j=1;j<=i;j++)
                    if(tnum<f[j])
                        tnum=f[j];
                for(j=1;j<=i;j++)
                    if(nextmin<f[j]&&f[j]!=tnum)
                        nextmin=f[j];
                for(j=1;j<i;j++)
                    if(f[j]!=f[j+1])
                    {flag=1;break;}
                if(tnum==0)
                {
                    tans[1]+=time;
                    break;
                }
                if(flag==0||f[1]==tnum)
                {
                    sum+=f[1];
                    f[1]-=d[1];
                    if(f[1]<0)f[1]=0;
                    tans[1]++;
                    time--;
                    continue;
                }
                for(j=1;j<=i;j++)
                {
                    if(f[j]==tnum&&d[j]!=0&&time>0)
                    {
                         sum+=f[j];
                        tans[j]++;
                        f[j]-=d[j];
                        time--;if(time<0)time=0;
                        if(f[j]<0)f[j]=0;
                    }
                    else if(f[j]==tnum&&d[j]==0&&time>0)
                    {
                        tans[j]+=time;
                        sum+=time*f[j];
                        time=0;
                        break;
                    }
                }
            }
            if(maxsum<sum)
            {
                maxsum=sum;
                for(j=1;j<=i;j++)
                    ans[j]=tans[j];
            }
            for(j=1;j<=n;j++)
                f[j]=tf[j];
        }
        for(i=1;i<=n;i++)
        {
            cout<<ans[i]*5;
            if(i!=n) cout<<", ";
            else cout<<endl;
        }
        cout<<"Number of fish expected: "<<maxsum<<endl;
    }    
    return 0;
}

这题写的很乱，要考虑的细节很多。贡献了2次TLE和6次WA后终于AC。。编码能力相当弱哇。。已经知道怎么算的，还错这么多次。。。