算法:枚举 + 贪心 + 多路归并
时间复杂度:$O(T \times N^2)$
枚举的是最远到达的鱼塘即将每一个鱼塘都枚举一遍,由此计算出总的钓鱼时间,每一次钓鱼时选取当前钓到鱼的数量最多的鱼塘,这里可以用堆来优化,在此可保证钓的鱼的总的数量是最多的。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int n, T;
int a[N], d[N], l[N], spend[N];
int work(int n, int T)
{
memset(spend, 0, sizeof(spend));
int res = 0;
for (int i = 1; i <= T; ++i) {
int t = 1;
for (int j = 1; j <= n; ++j) {
if (max(0, a[t] - d[t] * spend[t]) < max(0, a[j] - d[j] * spend[j])) {
t = j;
}
}
res += max(0, a[t] - d[t] * spend[t]);
spend[t]++;
}
return res;
}
int main()
{
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) {
cin >> l[i];
l[i] += l[i - 1];
}
cin >> T;
int res = 0;
for (int i = 1; i <= n; ++i) {
res = max(res, work(i, T - l[i])); // 考虑路费
}
cout << res << endl;
return 0;
}