一个藏得很深的多路归并问题
#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;
}
举个例子: