【題目描述】

有N個魚塘排成一排（N<100），每個魚塘中有一定數量的魚，例如：N=5時，如下表：

即：在第1個魚塘中釣魚第1分鐘內可釣到10條魚，第2分鐘內只能釣到8條魚，……，第5分鐘以后再也釣不到魚了。從第1個魚塘到第2個魚塘需要3分鐘，從第2個魚塘到第3個魚塘需要5分鐘，……

給出一個截止時間T(T<1000)，設計一個釣魚方案，從第1個魚塘出發，希望能釣到最多的魚。

假設能釣到魚的數量僅和已釣魚的次數有關，且每次釣魚的時間都是整數分鐘。

【輸入】

共5行，分別表示：

第1行為N；

第2行為第1分鐘各個魚塘能釣到的魚的數量，每個數據之間用一空格隔開；

第3行為每過1分鐘各個魚塘釣魚數的減少量，每個數據之間用一空格隔開；

第4行為當前魚塘到下一個相鄰魚塘需要的時間；

第5行為截止時間T。

【輸出】

一個整數（不超過2^31?1），表示你的方案能釣到的最多的魚。

【輸入樣例】

5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14

【輸出樣例】

76

【源程序】

#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <queue> #include <string> #include <vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 101 #define MOD 123 #define E 1e-6 using namespace std; #define fish first #define lake second priority_queue<pair<int, int> > heap; // pair表示先按照第一個元素降序排序，第一個元素相等時按照第二個元素降序排序 int t[N], f[N], d[N]; int main() {int n, T;cin >> n;for (int i = 1; i <= n; i++) //第1分鐘各個魚塘能釣到的魚的數量cin >> f[i];for (int i = 1; i <= n; i++) //每過1分鐘各個魚塘釣魚數的減少量cin >> d[i];for (int i = 1; i < n; i++) //當前魚塘到下一個相鄰魚塘需要的時間cin >> t[i];cin >> T; //截止時間int maxx = -INF;int walk_time = 0;for (int k = 1; k <= n; k++) //枚舉最遠走到的池塘的編號{int rest_time = T - walk_time; //計算剩余時間int ans = 0;for (int i = 1; i <= k; i++) //收集能夠釣魚的池塘的資料heap.push(make_pair(f[i], i));while (rest_time > 0 && heap.top().fish > 0) {pair<int, int> a = heap.top();heap.pop();ans += a.fish; //貪心選取魚最多的池塘a.fish -= d[a.lake]; //修改魚的數量heap.push(a); //堆維護rest_time--; //剩余時間變少}if (ans > maxx) //刷新最優解maxx = ans;walk_time += t[k]; //累計走路需要的時間}cout << maxx << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的鱼塘钓鱼（信息学奥赛一本通-T1373）的全部內容，希望文章能夠幫你解決所遇到的問題。

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