funiea,团子皇后,扑倒皇姐
结论:每次选择的区间一定满足首位元素相同。。
仔细想想其实挺显然的,如果不相同可以删掉多着的元素,对答案的贡献是相同的
那么设\(f[i]\)表示到第\(i\)个位置的最大价值,\(s[i]\)表示到\(i\)位置,\(a[i]\)的出现次数,转移方程为
\[f[i] = max(f_{j - 1} + a[i] * (s[i] - s[j] +1)^2)\]
满足\(a[i] = a[j]\)
看起来好像是可以斜率优化的样子,不过存在另外一种解释。。
具体看吧
感觉自己的斜率优化学的狠不到家啊,,有空补补qwq
#include<bits/stdc++.h> #define chmax(a, b) (a = (a > b ? a : b)) #define chmin(a, b) (a = (a < b ? a : b)) #define ll long long //#define int long long using namespace std; const int maxn = 1e6 + 10; inline int read() { int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, a[maxn], s[maxn], cnt[maxn]; ll f[maxn];//s[i] i位置的数第几次出? vector<int> v[maxn]; ll calc(int pos, ll val) { return f[pos - 1] + 1ll * a[pos] * val * val; } int lower(int x, int y) { int l = 1, r = n, ans = n + 1; while(l <= r) { int mid = l + r >> 1; if(calc(x, mid - s[x] + 1) >= calc(y, mid - s[y] + 1)) r = mid - 1, ans = mid; else l = mid + 1; } return ans; } main() { n = read(); for(int i = 1, siz, s; i <= n; i++) { s[i] = ++cnt[s = a[i] = read()]; while((((siz = v[s].size()) >= 2) && (lower(v[s][siz - 2], v[s][siz - 1]) <= lower(v[s][siz - 1], i)))) v[s].pop_back(); v[s].push_back(i); while(((siz = v[s].size()) >= 2) && (lower(v[s][siz - 2], v[s][siz - 1]) <= s[i]))v[s].pop_back(); f[i] = calc(v[s][v[s].size() - 1], s[i] - s[v[s][v[s].size() - 1]] + 1); } cout << f[n]; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论