牛客 1. set按步骤优化DP
原题链接
简单
作者:
流动的音符
,
2024-02-20 14:36:15
,
所有人可见
,
阅读 44
#include <bits/stdc++.h>
using namespace std;
const int N = 3 + 1e3;
int n, a[N], dp[N];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
auto fixMin = [&](set<int>& st) {
while (st.size() > 1) {
st.erase(--st.end());
}
};
auto fixMax = [&](set<int>& st) {
while (st.size() > 1) {
st.erase(st.begin());
}
};
for (int i = 1; i <= n; ++i) {
set<int> mn1, mx1;
set<int> mn2, mx2;
set<int> mn3, mx3;
set<int> mn4, mx4;
set<int> mn5, mx5;
for (int j = i; j <= n; ++j) {
// 注意for的顺序不能变
// 比如 mn5 依赖的是 i到j-1的 mn4和mx4
// 如果先修改mn4和mx4,mn4和mx4就变成i到j的
for (auto& k : mn5) {
dp[j] = max(dp[j], dp[i - 1] + k - a[j]);
}
for (auto& k : mx5) {
dp[j] = max(dp[j], dp[i - 1] + k - a[j]);
}
for (auto& k : mn4) {
mn5.insert(k * a[j]);
mx5.insert(k * a[j]);
}
for (auto& k : mx4) {
mn5.insert(k * a[j]);
mx5.insert(k * a[j]);
}
for (auto& k : mn3) {
mn4.insert(k - a[j]);
mx4.insert(k - a[j]);
}
for (auto& k : mx3) {
mn4.insert(k - a[j]);
mx4.insert(k - a[j]);
}
for (auto& k : mn2) {
mn3.insert(k * a[j]);
mx3.insert(k * a[j]);
}
for (auto& k : mx2) {
mn3.insert(k * a[j]);
mx3.insert(k * a[j]);
}
for (auto& k : mn1) {
mn2.insert(k - a[j]);
mx2.insert(k - a[j]);
}
for (auto& k : mx1) {
mn2.insert(k - a[j]);
mx2.insert(k - a[j]);
}
mn1.insert(a[j]);
mx1.insert(a[j]);
fixMin(mn1);
fixMin(mn2);
fixMin(mn3);
fixMin(mn4);
fixMin(mn5);
fixMax(mx1);
fixMax(mx2);
fixMax(mx3);
fixMax(mx4);
fixMax(mx5);
}
}
cout << *max_element(dp + 1, dp + n + 1);
return 0;
}