法一:思路
- 最后走到k个鱼塘,可以用
前缀和
求前面k个鱼塘赶路的时间
- 大根堆来维护当前哪个池塘能钓最多的鱼
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int a[N], d[N], T[N];
int n;
int main()
{
scanf("%d", &n);
//循环要分开写,不然读入数值会出问题
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++) scanf("%d", &d[i]);
for (int i = 2; i <= n; i ++)
{
scanf("%d", &T[i]);
T[i] += T[i - 1];
}
int Time;
scanf("%d", &Time);
int ans = -1;
for (int k = 1; k <= n; k ++)
{
int fish_time = Time - T[k];
priority_queue<PII> q;
for (int i = 1; i <= k; i ++)
q.push({a[i], i});//前k个鱼塘可钓鱼数,跟下标方便后续计算
int fish = 0; //前k个鱼塘能钓到的鱼
while (q.size() && fish_time > 0) //有鱼且还有时间钓鱼
{
PII t = q.top();
q.pop();
int var = t.second;
fish += t.first; //钓到的鱼
fish_time --; //减去一分钟
t.first -= d[var]; //减去每分钟鱼的减少量
if (t.first > 0) q.push({t.first, var});//只有钓到鱼,才需要入队
}
ans = max(ans, fish);
}
printf("%d\n", ans);
return 0;
}
法二:思路
- 我最初想的是所有鱼塘可钓鱼的数量是看全局时间的,所以赶快达到某个鱼塘答案就可能会更优,这样就很难做了,完全没思路
- 要明确一点是每个鱼塘可以钓到鱼的数量只和在当前这个鱼塘钓鱼的次数有关,所以每个鱼塘可钓鱼的数量是看自己的时间而非全局时间
- 所以当我们指明最终达到的鱼塘时,路上的时间是必须花费的,也是一定的,想要获得最优解就是从可钓鱼数量中找最大那几个就好了
- 先枚举最远走到哪个鱼塘。因为在每个鱼塘里能钓到的鱼只取决于在这个鱼塘钓的总时间。$n$
- 总钓鱼时间 =
T
- 路上的时间。
多路归并
:每次取当前每个序列的最大值
#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)
{ //所能钓到的鱼减去减少量
return max(0, a[k] - d[k] * spend[k]);
}
int work(int n, int T) //求到每个鱼塘能钓到的鱼
{
int res = 0;
memset(spend, 0, sizeof spend);
//下面要求在这个枚举到的鱼塘所钓的时间,所以要清空
for (int i = 0; i < T; i ++) //求在这个枚举到的鱼塘所钓的时间
{//两重循环的含义:在枚举到的每分钟下每个鱼塘能钓到最多鱼的数量
int t = 1;//存下枚举
for (int j = 1; j <= n; j ++)//
if (get(j) > get(t))
t = j;
res += get(t);
spend[t] ++;
}
return res;
}
int main()
{
int 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 ++)
{
scanf("%d", &l[i]);
l[i] += l[i - 1]; //到每个鱼塘所需的时间
}
scanf("%d", &T);
int res = 0;
for (int i = 1; i <= n; i ++)
res = max(res, work(i, T - l[i]));
printf("%d\n", res);
return 0;
}