【斜率优化】牛客练习赛40D 小A与最大子段和
题目传送门
官方题解
题意是说找到一个连续子段,使得\sum_{i}^{j}a_i \times i最大,也就是说每个数要乘上自己在子段里的位置。
官方题解就是说,令f[i]表示前i个数字的答案。f_{i}=\max_{j=0}^{i-1} (\sum_{k=j+1}^{i}a_k \times {(k-j)})这样每个a就可以和自己对应的坐标相乘,而j又是固定的,所以可以直接用前缀和把题目简化掉。
要截距最大化,斜率不单调,维护整个上突壳,在上突壳上二分找左边斜率小于当前,右边斜率大于当前的点。注意答案的初始化要为负数,因为答案可能为负。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+233;
ll a[maxn],b[maxn],f[maxn];
int q[maxn];
int l=1,r=1;
int n;
int brf(int k)
{
if(l == r) return q[l];
int L=l,R=r;
while(L<R)
{
int mid=(L+R)>>1;
if(b[q[mid + 1]] * q[mid + 1] - a[q[mid + 1]] - b[q[mid]] * q[mid] + a[q[mid]]
>= b[k] * (q[mid + 1] - q[mid])) L = mid + 1;
else R
… Read the rest