題目描述
? ? ? ? 有N個魚塘排成一排（N＜100），每個魚塘中有一定數量的魚，例如：N=5時，如下表：
? ? ? ? 即：在第1個魚塘中釣魚第1分鐘內可釣到10條魚，第2分鐘內只能釣到8條魚，......，第5分鐘以后再也釣不到魚了。從第1個魚塘到第2個魚塘需要3分鐘，從第2個魚塘到第3個魚塘需要5分鐘，......
? ? ? ? 給出一個截止時間T（T＜1000），設計一個釣魚方案，從第1個魚塘出發，希望能釣到最多的魚。假設能釣到魚的數量僅和已釣魚的次數有關，且每次釣魚的時間都是整數分鐘。
?
輸入格式
? ? ? ? 共5行，分別表示：
? ? ? ? 第一行為整數N；
? ? ? ? 第二行為第1分鐘各個魚塘能釣到的魚的數量，每個數據之間用一空格隔開；
? ? ? ? 第三行為每過1分鐘各個魚塘釣魚數的減少量，每個數據之間用一空格隔開；
? ? ? ? 第四行為當前魚塘到下一個相鄰魚塘需要的時間；
? ? ? ? 第五行為截止時間T。
?
輸出格式
? ? ? ? 僅一個整數，表示能釣到的最多的魚。
?
輸入樣例
5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14
?
輸出樣例
76
?
題解
? ? ? ? 我們其實可以枚舉從魚塘$1$走到魚塘$i$，在這過程中釣到的魚的最大值。
? ? ? ? 我們先提前減去來往魚塘之間的時間，這樣實際上就是轉換成每次任意選第$1$到第$i$個魚塘來釣魚，用堆維護一下即可。
#include <iostream> #include <cstdio> #include <queue> #include <map>#define MAX_N (100 + 5)using namespace std;int n; int a[MAX_N], b[MAX_N], c[MAX_N]; int t; priority_queue <pair <int, int> > q; int ans;int main() {scanf("%d", &n);for(register int i = 1; i <= n; ++i){scanf("%d", a + i);}for(register int i = 1; i <= n; ++i){scanf("%d", b + i);}for(register int i = 1; i < n; ++i){scanf("%d", c + i);}scanf("%d", &t);int tmp, sum, val, idx;for(register int i = 1; i <= n && t > 0; ++i){while(!q.empty()) q.pop();for(register int j = 1; j <= i; ++j){q.push(make_pair(a[j], j));}tmp = t;sum = 0;while(tmp-- && !q.empty()){val = q.top().first;idx = q.top().second;q.pop();sum += val;val -= b[idx];if(val > 0) q.push(make_pair(val, idx));}ans = max(ans, sum);t -= c[i];}printf("%d", ans);return 0; }
?
