题解：P11333 [NOISG 2020 Finals] Discharging

· · 题解

分析

首先我们可以用一个提前算贡献的方法，容易定义 DP 状态 f_{i} 表示在 i 这里分一个组时此时序列的最小等待时间之和。然后有 DP 方程：

f_i=\min_{j=1}^{i-1} (f_j+(n-j)\max_{k=j+1}^i a_k)

用 st 表优化即可，时间复杂度 O(n^2)，无法接受。

我们观察这个式子的性质，我们发现里面的那个 \max 非常烦人，于是我们考虑有什么数会当成里面的那个数并且最优。

我们发现前缀最大值必须当里面的 \max，所以我们考虑将所有前缀最大值拎出来，记第 i 个前缀最大值为 d_i，那么状态依然是这个，但是转移方程变为：

f_i=\min_{j=1}^{i-1}(f_j+(n-d_{j+1}+1)d_i)

变形一下：

f_i=\min_{j=1}^{i-1}(f_j-d_i \times d_{j+1})+(n+1)d_i

我们发现这是一个斜率优化的形式，而且 d_{j+1} 具有单调性，所以我们可以用单调队列 + 二分维护，时间复杂度 O(n \log n)。

代码

::::info[代码]

#include <cstdio>
#include <algorithm>
#define N 1000005
#define ll long long
using namespace std;
int n,a[N],d[N],mx,cnt,s[N],t;
ll f[N];
inline int ef(int x){
    int l=1,r=t,midd=1,mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(1ll*x*(d[s[mid+1]+1]-d[s[mid]+1])<f[s[mid+1]]-f[s[mid]]){
            midd=mid;//按照斜率二分
            r=mid-1;
        }
        else l=mid+1;
    }
    return s[midd];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]>mx) d[++cnt]=i;
        mx=max(mx,a[i]);
    } 
    s[++t]=0;
    for(int i=1;i<=cnt;i++){
        int p=ef(a[d[i]]);
        f[i]=f[p]+1ll*a[d[i]]*(n-d[p+1]+1);//dp
        while(t>1&&(__int128)(f[s[t]]-f[s[t-1]])*(d[i+1]-d[s[t]+1])>(__int128)(f[i]-f[s[t]])*(d[s[t]+1]-d[s[t-1]+1])) t--;//按照斜率大小弹出
        s[++t]=i;
    } 
    printf("%lld",f[cnt]);
    return 0;
}

::::