鱼塘钓鱼(多路归并）

有 N
个鱼塘排成一排，每个鱼塘中有一定数量的鱼，例如：N=5
时，如下表：

鱼塘编号	1	2	3	4	5
第1分钟能钓到的鱼的数量 （1…1000）	10	14	20	16	9
每钓鱼1分钟钓鱼数的减少量（1…100)	2	4	6	5	3
当前鱼塘到下一个相邻鱼塘需要的时间（单位：分钟）	3	5	4	4

即：在第 $1$ 个鱼塘中钓鱼第 $1$ 分钟内可钓到 $10$ 条鱼，第 $2$ 分钟内只能钓到 $8$ 条鱼，……，第 $5$ 分钟以后再也钓不到鱼了。

从第 $1$ 个鱼塘到第 $2$ 个鱼塘需要 $3$ 分钟，从第 $2$ 个鱼塘到第 $3$ 个鱼塘需要 $5$ 分钟，……

给出一个截止时间 $T$，设计一个钓鱼方案，从第 $1$ 个鱼塘出发，希望能钓到最多的鱼。

假设能钓到鱼的数量仅和已钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。

输入格式

共 $5$ 行，分别表示：

第 $1$ 行为 $N$；

第 $2$ 行为第 $1$ 分钟各个鱼塘能钓到的鱼的数量，每个数据之间用一空格隔开；

第 $3$ 行为每过 $1$ 分钟各个鱼塘钓鱼数的减少量，每个数据之间用一空格隔开；

第 $4$ 行为当前鱼塘到下一个相邻鱼塘需要的时间；

第 $5$ 行为截止时间 $T$。

输出格式

一个整数（不超过$231-1$），表示你的方案能钓到的最多的鱼。

数据范围

$1\le N\le 100$,
$1\le T\le 1000$

输入样例：

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

输出样例：

76

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;

int a[N], d[N], l[N], spend[N];

int get(int k) {                                //第i分钟在第k个鱼塘钓到鱼的数量
return max(0, a[k] - d[k] * spend[k]);
}

int work(int n, int T) {                        //只走前n个鱼塘，且时间为T的最大收益
int res = 0;
memset(spend, 0, sizeof spend);
for (int i = 0; i < T; i ++ ) {             //按分钟遍历
int t = 1;                              //t表示第i分钟第t的鱼塘的鱼最多，初始为1号鱼塘
for (int j = 1; j <= n; j ++ )          //第i分钟在前n个鱼塘的最大收益
if (get(j) > get(t))
t = j;

res += get(t);
spend[t] ++ ;                           //在t号鱼塘逗留时间+1
}
return res;
}

int main() {
int n, T;                                   //n个鱼塘，截止时间为T
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i]; //各鱼塘第一分钟产鱼量
for (int i = 1; i <= n; i ++ ) cin >> d[i]; //各鱼塘每一分钟减鱼量
for (int i = 2; i <= n; i ++ ) {            //从第一个鱼塘到第i个鱼塘之间的距离
cin >> l[i];
l[i] += l[i - 1];                       //因为这步求前缀和，所以前面下标i要从1开始
}
cin >> T;

int res = 0;
for (int i = 1; i <= n; i ++ )              //从第一个鱼塘出发，遍历n个鱼塘
res = max(res, work(i, T - l[i]));      //只去前i个鱼塘的最大收益，这里已经减去路上所用时间

cout << res << endl;
}

原文地址：https://blog.csdn.net/2201_75859030/article/details/136997752

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！