題意：
? ? ? 你有H小時（H*12個單位）時間去用，有n個魚池在一條直線上，一開始你在1的位置，可以選擇在某些魚池上釣魚，但是如果持續在一個魚池上釣魚釣魚速度回成線性減少，初始每個時間單位釣fi條，然后下一個時間單位釣fi-di條，再下一個fi-di-di條，每個魚池和他下一個魚池的距離是ti個時間單位，最后你可以聽到任意一個魚池上，問最多釣多少條魚，然后輸出在個魚池的停留時間和最多的魚數。


思路：
? ? ? 枚舉終點，對于每一個枚舉的終點也就是相當于擁有了一段可以隨意選的魚塘，然后我們在枚舉區間沒一個單位一個單位的去選，每次都去選最優的一個，然后加到總和里，然后把當前這個魚塘的速度改變下，這里可以用優先隊列去實現，每次拿出一個最優的，然后更新總和，然后把拿出來這個更改數值后存回隊列，還有就是注意輸出要求，答案不確定的時候輸出什么啥的一些小細節。


#include<queue>
#include<stdio.h>
#include<string.h>


using namespace std;


typedef struct NODE
{
? ? int id ,f ,d;
? ? friend bool operator < (NODE a ,NODE b)
? ? {
? ? ? ? return a.f < b.f || a.f == b.f && a.id > b.id;
? ? }
}NODE;


int main ()
{
? ? int n ,h ,i ,j ,sum ,tsum;
? ? int ans[30] ,tans[30];
? ? int tt[30];
? ? NODE node[30];
? ? int mk = 0;
? ? while(~scanf("%d" ,&n) && n)
? ? {
? ? ? ? if(mk) printf("\n");
? ? ? ? mk = 1;
? ? ? ? scanf("%d" ,&h);
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%d" ,&node[i].f);
? ? ? ? ? ? node[i].id = i;
? ? ? ? }
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? scanf("%d" ,&node[i].d);
? ? ? ? for(i = 1 ;i < n ;i ++)
? ? ? ? scanf("%d" ,&tt[i]);
? ? ? ? memset(ans ,0 ,sizeof(ans));
? ? ? ? sum = -1;
? ? ? ? int s = 0;
? ? ? ? h *= 12;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? if(i == 1) s = 0;
? ? ? ? ? ? else s += tt[i-1];
? ? ? ? ? ? if(s > h) break;
? ? ? ? ? ? priority_queue<NODE>q;
? ? ? ? ? ? NODE xin ,tou;
? ? ? ? ? ? for(j = 1 ;j <= i ;j ++)
? ? ? ? ? ? q.push(node[j]);
? ? ? ? ? ? int hh = h - s;
? ? ? ? ? ? memset(tans ,0 ,sizeof(tans));
? ? ? ? ? ? tsum = 0;
? ? ? ? ? ? while(hh--)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? tou = q.top();
? ? ? ? ? ? ? ? q.pop();
? ? ? ? ? ? ? ? tans[tou.id] += 5;
? ? ? ? ? ? ? ? tsum += tou.f;
? ? ? ? ? ? ? ? tou.f -= tou.d;
? ? ? ? ? ? ? ? if(tou.f < 0) tou.f = 0;
? ? ? ? ? ? ? ? q.push(tou);
? ? ? ? ? ? }
? ? ? ? ? ? if(tsum > sum)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? for(j = 1 ;j <= n ;j ++)
? ? ? ? ? ? ? ? ans[j] = tans[j];
? ? ? ? ? ? ? ? sum = tsum;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? if(i == n) printf("%d\n" ,ans[i]);
? ? ? ? ? ? else printf("%d, ",ans[i]);
? ? ? ? }
? ? ? ? printf("Number of fish expected: %d\n" ,sum);
? ? }
? ? return 0;
}

總結

以上是生活随笔為你收集整理的POJ1042 贪心钓鱼的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。