鏈接：https://vjudge.net/problem/POJ-1042
思路：貪心題。首先中途花費的時間總和只跟最終的終點有關(guān)耕拷，所以考慮枚舉終點。然后用一個優(yōu)先隊列儲存當前能釣魚的總量副瀑，每次取出最大的舱污，然后減去減少量再放入隊列想幻，注意如果存在相等的釣魚總量則取魚塘序號（靠前面）較小的哪一個粱栖，然后一直直到時間<5就結(jié)束。

代碼：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

const int maxn = 30;

//魚塘脏毯，注意排序時如果相等就返回魚塘序號較小的那一個
struct fish{
    int f,d,t,p;
    bool operator<(const fish &a1)const{
        if(f==a1.f) return p>a1.p; 
        return f<a1.f;
    }
}ff[maxn];

int cc[maxn],dd[maxn];
int n,h;



int main(){
    int o = 0;
    while(scanf("%d",&n)&&n){
        memset(dd,0,sizeof(dd));
        scanf("%d",&h);
        for(int i=0;i<n;++i)scanf("%d",&ff[i].f);
        for(int i=0;i<n;++i)scanf("%d",&ff[i].d);
        for(int i=0;i<n-1;i++)scanf("%d",&ff[i].t);
        for(int i=0;i<n;i++)ff[i].p = i;
        int res = 0;
        for(int i=0;i<n;i++){
           int times = h*60; 
            memset(cc,0,sizeof(cc));
         priority_queue<fish> q1;
            int ans = 0;

           for(int j=0;j<i;j++)
               times-=ff[j].t*5;//枚舉終點闹究，除去中間花費的時間

            for(int j=0;j<=i;++j)
             q1.push(ff[j]);

            while(times>=5&&!q1.empty()){
                fish z = q1.top();
                q1.pop();
                times-=5;
                cc[z.p]++;
                ans+=z.f;
                z.f= z.f - z.d; //扣去每次釣魚后的魚塘總量減少量，再入隊
                if(z.f<0)z.f=0;
                q1.push(z);
                }
            if(ans>res){
                res = ans;
                for(int k=0;k<n;k++){
                dd[k] = cc[k];
                }
            }

            else if(ans==res){
                int judge = 0;
                for(int k=0;k<n;k++){
                    if(cc[k]>dd[k]){judge = 1;break;}
                    else if(cc[k]<dd[k])break;
                    else continue;
                }

                if(judge){
                    for(int k=0;k<n;k++){
                        dd[k] = cc[k];
                    }
                }
            }

        }
        if(o++)printf("\n");
        for(int i=0;i<n-1;i++){
        printf("%d, ",dd[i]*5);
        }
        printf("%d\n",dd[n-1]*5);
        printf("Number of fish expected: %d\n",res);
    }
    return 0;
}