[TIOJ 1399] 超級撈魚活動

這題是問周逸(周強)才會的，我原本一直在想DP，會變成很奇怪的轉移，看起來會用到甚麼四邊形優化，但其實只要 greedy 就好了QQ

作法：

如果確定最遠要撈到哪個魚池之後，把走路用掉的時間扣掉(因為不會回頭走)，這樣最好的情形就是每次都選可以撈到最魚的魚池撈，撈到時間結束就好了。所以可以用一個 priority_queue 維護現在撈了哪些數量的魚，還有剩下多少時間，根目前撈的魚的數量總和。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100000+10 ;
 
int f[maxn],d[maxn],t[maxn] ;
priority_queue< int,vector<int>,greater<int> > pq ;
 
main()
{
    int T,n ;
    while(scanf("%d%d",&T,&n)!=EOF)
    {
        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;i++) scanf("%d",&t[i]) ;
        LL ans=0LL , sum=0LL ;
        while(!pq.empty()) pq.pop() ;
        for(int i=1;i<=n;i++)
        {
            T-=t[i] ;
            while(T<0 && !pq.empty())
                sum-=pq.top() , pq.pop() , T++ ;
            if(T<0 || (T==0 && pq.empty())) break ;
            for(int j=0;;j++)
            {
                int val=f[i]-j*d[i] ;
                if(val<=0) break ;
                if(T>0) pq.push(val) , sum+=val , T-- ;
                else if(pq.top()<val)
                    sum+=val-pq.top() , pq.pop() , pq.push(val) ;
                else break ;
            }
            ans=max(ans,sum) ;
        }
        printf("%lld\n",ans) ;
    }
}