CF660F Bear and Bowling 4 [斜率优化动态规划]

$BearandBowling4$Bear and Bowling 4

$Description$Description
给一个长度为 $N$N 的序列 $\left\{a_i\right\}${ai​}, 求 $\underset{}{\overset{x=1}{\max }}(\sum _{i=1}^{k}i\cdot a_{x+i-1})$x=1maxN−k+1​(i=1∑k​i⋅ax+i−1​)

$1\le n\le 2\times 10^5,\mid a_i\mid \le 10^7$1≤n≤2×105,∣ai​∣≤107

$最初想法$最初想法
$暴力$暴力: $O\left(N\right)$O(N) 枚举 $k$k, 再配合前缀和 $O\left(N\right)$O(N) 计算答案, 取最优值, 总共 $O\left(N^2\right)$O(N2).
正解要斜率优化, 回去学习…

$正解部分$正解部分
$n$n 年后, 斜率优化看懂一点了… 没学过的可以点击 这里.

设 $su{m}_1\left[i\right]$sum1​[i] 表示前 $i$i 个 $a_i$ai​ 的前缀和, $su{m}_2\left[i\right]$sum2​[i] 表示前 $i$i 个 $i\ast a_i$i∗ai​的前缀和, $val[i,j]$val[i,j]表示 $i,j$i,j之间的价值 .
则 $val[i,j]=su{m}_2\left[j\right]-su{m}_2[i-1]-(i-1)\ast \left(su{m}_1\right[j]-su{m}_1[i-1\left]\right)$val[i,j]=sum2​[j]−sum2​[i−1]−(i−1)∗(sum1​[j]−sum1​[i−1])

化简为 $y=kx+b$y=kx+b 的形式进行 斜率优化,
$(i-1)su{m}_1[i-1]-su{m}_2[i-1]=(i-1)su{m}_1\left[j\right]+val[i,j]-su{m}_2\left[j\right]$(i−1)sum1​[i−1]−sum2​[i−1]=(i−1)sum1​[j]+val[i,j]−sum2​[j]
此时

• $y=(i-1)su{m}_1[i-1]-su{m}_2[i-1]$y=(i−1)sum1​[i−1]−sum2​[i−1]
• $k=su{m}_1\left[j\right]$k=sum1​[j]
• $x=i-1$x=i−1
• $b=val[i,j]-su{m}_2\left[j\right]$b=val[i,j]−sum2​[j].

鉴于求的是最大值, 所以维护上凸壳.
且 $k$k的正负无法确定, 于是不能使用弹掉队首的方法去找最优决策点 , 只能使用二分去查找队列中第一个比 小于等于 $k$k 的斜率 .

于是枚举右端点 $j$j 的同时将 $j$j 作为一个新的决策加入斜率优化的单调队列中, 用来对以后的 $j$j 提供决策 $i$i,

$实现部分$实现部分

#include<cstdio>
#include<algorithm>
#define reg register
typedef long long ll;

const int maxn = 2e5 + 10;

int N;
int A[maxn];

ll Q[maxn];
ll sum1[maxn];
ll sum2[maxn];

double X(int i){ return i; }

double Y(int i){ return i*sum1[i] - sum2[i]; }; //!

double slope(int i, int j){ return ( Y(i)-Y(j) ) / ( X(i)-X(j) ); }

ll Calc(int i, int j){ return sum2[j]-sum2[i]-1ll*i*(sum1[j]-sum1[i]); }

int main(){
        scanf("%d", &N);
        for(reg int i = 1; i <= N; i ++){
                scanf("%d", &A[i]);
                sum1[i] = sum1[i-1] + A[i];
                sum2[i] = sum2[i-1] + 1ll*A[i]*i;
        }
        int tail = 0; ll Ans = 0;
        for(reg int j = 1; j <= N; j ++){
                ll k = sum1[j];
                int l = 0, r = tail;
                while(l < r){
                        int mid = l+r >> 1;
                        if(slope(Q[mid], Q[mid+1]) > k) l = mid+1;
                        else r = mid;
                }
                int i = Q[r];
                Ans = std::max(Ans, Calc(i, j));
                while(tail >= 1 && slope(Q[tail], Q[tail-1]) < slope(Q[tail], j)) tail --;
                Q[++ tail] = j;
        }
        printf("%I64d\n", Ans);
        return 0;
}