[TIOJ] 1399. 超級撈魚活動

題目連結:http://tioj.infor.org/problems/1399

---

一直都只想到$O(nT^2)$的做法，原來是狀態(甚至是方向)的整個錯了，這題應該可以變成狀態是$dp[i]$代表前$i$個魚池都不會再撈時，最多可以撈到幾隻(而且要記錄每次是撈了多少的魚，但不用照順序)。那轉移的話就變得容易了，因為就代表你要在可以撈的那些魚的量中與先前的比較那些可以多擺進去，假設原本可以撈到的魚量是一條由大到小排好的單調隊列的話，而現在撈到的魚量也是一條單調隊列的話，那就很容易可以用merge sort的方式將其排序好，而顯然要讓自己這條是單調隊列的話，非常容易，畢竟按照次數來看就是$F_i, F_i - D_i, F_i-2D_i, \cdots $，所以轉移也僅需要O(T)的時間，總複雜度就順利地變成$O(nT)$了

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second

const int N = 100000 + 5;

PII arr[N];
int T[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int t, n;
	while(cin>>t>>n){
		for(int i=1;i<=n;i++) cin>>arr[i].FF;
		for(int i=1;i<=n;i++) cin>>arr[i].SS;
		for(int i=1;i<=n;i++){
			cin>>T[i];
			T[i]+=T[i-1];
		}
		lld ans=0;
		vector<int> cur;
		for(int i=1;i<=n;i++){
			vector<int> nxt;
			lld nans=0;
			int pp=0;
			for(int j=0;j<t-T[i];j++){
				while(pp < (int)cur.size() and cur[pp] > arr[i].FF-arr[i].SS*j){
					if((int)nxt.size() >= t-T[i]) break;
					nxt.PB(cur[pp++]);
					nans += max(0, nxt.back());
				}
				if((int)nxt.size() >= t-T[i]) break;
				nxt.PB(arr[i].FF-arr[i].SS*j);
				nans += max(0, nxt.back());
			}
			swap(cur, nxt);
			ans = max(ans, nans);
		}
		cout<<ans<<'\n';
	}
	return 0;
}