(堆优化 + 贪心)
如果知道了取到最大值的情况下,人最后在第i个鱼塘里钓鱼,那么在路上的时间是固定的,不必浪费时间的走来走去,每次按照贪心思想确定在哪些池塘钓鱼,经过n次后确定最终得到的一定是最优方案。枚举终点,然后每次找到最大的,减去最大的就行了,找最大这一过程通过堆来进行优化.
时间复杂度
O(T∗nlogn)
C++ 代码
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> Pii;
const int N = 120;
int a[N], d[N], t[N], s[N];
int n;
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 >> t[i];
s[i] = s[i - 1] + t[i];
}
int T;
cin >> T;
int ans = 0;
for (int i = 1; i <= n && s[i] <= T; i++) { //枚举每个最后可以到达的位置i
priority_queue<Pii> que;
for (int j = 1; j <= i; j++) { //前i个位置维护最大的钓鱼数,最大堆维护
que.push({a[j], d[j]});
}
int res = 0, u = T - s[i]; //在满足所要求的时间条件下,累加所维护的最大钓鱼数
for (int j = 1; j <= u; j++) {
Pii p = que.top();
que.pop();
if (p.first <= 0) {
break;
}
res += p.first;
p.first = p.first - p.second;
que.push({p.first, p.second});
}
ans = max(ans, res);
}
cout << ans << endl;
return 0;
}
(动态规划)
设在池塘i花了k个单位时间钓鱼,从池塘i-1走到池塘i要花t[i-1]的时间。那么f[i][j]就等于opt[i][j-t[i-1]-k](即到上一个池塘花j-池塘i-1到池塘i的时间-k的单位时间的最优解)加上在池塘i花k个单位时间钓到的鱼
$f[i][j]=max f[i−1][j−t[i−1]−k]+k∗a[i]−d[i]−2∗d[i]−3∗d[i]−…−(k−1)∗d[i]$
化简得:
$f[i][j]=max f[i−1][j−t[i−1]−k]+k∗a[i]−k∗(k−1)/2∗d[i]$
时间复杂度
O(T * n)
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 120, M = 1020;
int a[N], d[N], t[N], f[N][M];
int n;
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 = 1; i < n; i++) {
cin >> t[i];
}
int T;
cin >> T;
memset(f, -1, sizeof(f)); //初始化为-1,代表没有用过该值
f[0][0] = 0;
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= T; j++) {
for (int k = 0; k <= j - t[i - 1]; k++) { //枚举满足条件的时间k
if (a[i] > (k - 1) * d[i] && f[i - 1][j - t[i - 1] - k] != -1) { //a[i]未减少到0且前面的状态已经求出,可求得f[i][j]
f[i][j] = max(f[i][j], f[i - 1][j - t[i - 1] - k] + k * a[i] - k*(k - 1)/2 * d[i]);
ans = max(ans, f[i][j]);
}
}
}
}
cout << ans << endl;
return 0;
}