题目链接

bzoj4709: [Jsoi2011]柠檬

题解

斜率优化 设 \(f[i]\) 表示前 \(i\)个数分成若干段的最大总价值。 对于分成的每一段，左端点的数、右端点的数、选择的数一定是相同的。如果不相同则可以从这个段里删去这个数，答案会更优。 于是就有转移：\(f_i=f_{j-1}+a·(c_i-c_j+1)^2\ ,\ j\le i\ ,\ a_j=a_i\) ，其中 \(a\) 表示原序列，\(c\) 表示这个位置时这个数第几次出现 显然这个式子可以斜率优化，整理得：$ac_i 2(c_j - 1) + f_i - a c_i^2 = f_{j-1} + a·(c_j-1)^2 $ ，那么 \(y\) 是 \(f_{j-1}+a (c_j-1)^2\) ，\(k\) 就是 \(ac_i\) ，\(x\) 是 \(2(c_j-1)\) ，\(b\) 是 \(f_i-ac_i^2\) . 这里 \(k\) 单调递增，\(x\) 递增，求\(b\)的最大值， 直接对于每个a_i维护上凸壳。在凸壳上二分。 时间复杂度 \(O(n\log n)\)

代码

#include<vector> #include<cstdio> #include<algorithm> #define gc getchar() #define pc putchar inline int read() { int x = 0,f = 1; char c = gc; while(c < '0' || c > '9') c = gc; while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc; return x * f; } #define LL long long void print(LL x) { if(x >= 10) print(x / 10); pc(x % 10 + '0'); } #define y(i) (f[i - 1] + a[i] * squ(c[i] - 1)) #define x(i) 2 * (c [i] - 1) inline LL squ(LL x) { return x * x; } const int maxn = 1000007; std::vector<int>v[maxn]; LL f[maxn],a[maxn],c[maxn],cnt[maxn] ; int main() { int n = read(); for(int i = 1;i <= n;++ i) { a[i] = read(); c[i] = ++ cnt[a[i]]; int t; while((t = v[a[i]].size() - 1) > 0 && (x(i) - x(v[a[i]][t])) * (y(v[a[i]][t - 1]) - y(v[a[i]][t])) - (y(i) - y(v[a[i]][t])) * (x(v[a[i]][t - 1]) - x(v[a[i]][t])) > 0) v[a[i]].pop_back(); v[a[i]].push_back(i); int l = 1,r = v[a[i]].size() - 1,ans = 0; while(l <= r) { int mid = l + r >> 1; if(f[v[a[i]][mid] - 1] + a[i] * squ(c[i] - c[v[a[i]][mid]] + 1) > f[v[a[i]][mid - 1] - 1] + a[i] * squ(c[i] - c[v[a[i]][mid - 1]] + 1)) ans = mid,l = mid + 1; else r = mid - 1; } f[i] = f[v[a[i]][ans] - 1] + a[i] * squ(c[i] - c[v[a[i]][ans]] + 1); } print(f[n]); return 0; } /* 5 2 2 5 2 3 */

转载于:https://www.cnblogs.com/sssy/p/9762997.html