解题思路
通过赋值无穷,标记非法状态。取最大值,所以标记负无穷
入口:可以买也可以不买,也就是手中无货且不在冷冻期的状态,也就是处于 2 状态
出口:因为是最大利润,所以手中肯定没货,也就是 1 2 状态
滚动变量优化空间:第 $i$ 层只依赖 $i - 1$ 层,所以从小到大迭代,计算到第 $i$ 层时 $i - 1$ 层已经计算过,所以可以用三个变量记录一下
代码
原始做法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int w[N], f[N][3];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
f[0][0] = f[0][1] = -0x3f3f3f, f[0][2] = 0;
for (int i = 1; i <= n; i++) {
f[i][0] = max(f[i - 1][0], f[i - 1][2] - w[i]);
f[i][1] = f[i - 1][0] + w[i];
f[i][2] = max(f[i - 1][1], f[i - 1][2]);
}
cout << max(f[n][1], f[n][2]) << endl;
return 0;
}
滚动变量优化空间
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int w, f[3];
int main() {
int n;
cin >> n;
f[0] = f[1] = -0x3f3f3f, f[2] = 0;
for (int i = 1; i <= n; i++) {
cin >> w;
int a = max(f[0], f[2] - w);
int b = f[0] + w;
int c = max(f[1], f[2]);
f[0] = a;
f[1] = b;
f[2] = c;
}
cout << max(f[1], f[2]) << endl;
return 0;
}