#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
//首先直觉上你是不知道等到第几秒去下一个鱼塘的,那么我们只需要从每一列第一个中最大的数即可。
//spend[N] 本质上是st数组的巧用,标记每个鱼塘被选了几次
const int N = 110;
int num[N], d[N], s[N], spend[N];
int get(int k) {
//记得减到后面就会没鱼了;
return max(0, num[k] - d[k] * spend[k]);
}
int work(int n, int T) {
memset(spend, 0, sizeof spend);
int res = 0;
//挑选出前T大的数;
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 >> num[i];//各个鱼塘能调到鱼的数量
for (int i = 1; i <= n; i ++ ) cin >> d[i];//各个鱼塘钓鱼数的减少量
//算出从1到i的时间
for (int i = 2; i <= n; i ++ ) {
cin >> s[i];
s[i] += s[i - 1];
}
cin >> T;
int res = 0;
//枚举最后到了哪个鱼塘
for (int i = 1; i <= n; i ++ ) {
res = max (res, work(i, T - s[i]));
}
cout << res << endl;
return 0;
}
堆做法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int num[N], d[N], s[N], num1[N];
int work(int n, int T) {
priority_queue<PII> heap;
//用堆做的困难点在于num数组需要备份+堆清空(重新定义)
for (int i = 1; i <= n; i++) num1[i] = num[i];
for (int i = 1; i <= n; i++) heap.push({num[i], i});
int res = 0;
for (int i = 1; i <= T; i ++ ) {
res += heap.top().first;
int id = heap.top().second;
heap.pop();
num1[id] = max(0, num1[id] - d[id]);
heap.push({num1[id], id});
}
return res;
}
int main() {
int n, T;
cin >> n;
for (int i = 1; i <= n; i++) cin >> num[i];
for (int i = 1; i <= n; i++) cin >> d[i];
for (int i = 2; i <= n; i ++ ) {
cin >> s[i];
s[i] += s[i - 1];
}
cin >> T;
int res = 0;
for (int i = 1; i <= n; i++) {
res = max(res, work(i, T - s[i]));
}
cout << res << endl;
}