P11333 [NOISG 2020 Finals] Discharging

题意

给定一个长度为

n

的正整数序列

a

，可以划分为若干段。假设划分为

k

段，设每一段的最大值为

v_i

，设

s_i

表示

\sum_{j=1}^{i}v_j

，

len_i

表示第

i

段的长度，则一种划分方案的费用为

\sum_{i=1}^{k}len_i\times s_i

。求最小费用。

1\le n\le 10^6

。

设

f_{i}

表示前

i

个顾客的最小充电时间。

考虑“延后贡献”。

设

f_i

表示前

i

个的最小往后总贡献。

f_i &=\min_{j=0}^{i-1}(f_j+(\max_{k=j+1}^{i}a_k)\times(n-j))\\ \end{aligned}$$ 然后我们发现一个性质：每段的最大值递增时最优。 考虑证明。 若有相邻两段减或者先相等，显然可以把这两段融合使其更优。 也就是说，实际上只有前缀最大值在作为当前段的最大值时，才会使策略最优。 设 $p_i$ 表示前缀 $i$ 中最大值的最早位置。定义 $v_i$ 为前缀最大值，那么转移式可以优化为。

f_{i}=\min_{j=0}^{i-1}(f_j+a_{p_i}\times (n-j))

系数拆分。

f_i=v_{i}\times n+\min_{j=0}^{p_i-1}(f_j-v_{i}\times j)

考虑斜率优化，维护下凸壳。 设 $j_2>j_1$ 且使用 $j_2$ 位置的策略更优。 $$\begin{aligned} f_{j_2}-v_i\times j_2 &< f_{j_1}-v_i\times j_1\\ f_{j_2}-f_{j_1} &< v_i\times(j_2-j_1)\\ \end{aligned}$$ 令 $y_i=f_i,x_i=i,k_i=v_i$。

\frac{y_{j_2}-y_{j_1}}{x_{j_2}-x_{j_1}}<k_i

由于 $x_i$ 单增，$k_i$ 单调不降，可以直接套上斜率优化，要求单调队列内

k_i<K_{j_1,j_2}<K_{j_2,j_3}<\dots<K_{j_{m-1},j_{m}}

## 代码 ```cpp #include<bits/stdc++.h> #define ll long long using namespace std; template<typename T> inline void read(T &x){ T w=1; x=0; char c=getchar(); while(!isdigit(c)){ if(c=='-') w=-1; c=getchar(); } while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar(); x*=w; } template<typename T> inline void write(T x){ if(x<0) putchar('-'),x=(~x)+1; if(x>9) write(x/10); putchar(x%10^48); } const ll N=1e6+10,inf=1e16; ll n,a[N],ma[N]; ll f[N],x[N],y[N],k[N]; double lv(ll a,ll b){ return (double)(y[a]-y[b])/(double)(x[a]-x[b]); } int main(){ // freopen(".in","r",stdin); // freopen(".out","w",stdout); read(n); for(int i=1;i<=n;i++) read(a[i]),k[i]=max(k[i-1],a[i]),f[i]=inf; deque<ll>q; q.push_back(0); for(int i=1;i<=n;i++){ while(q.size()>=2){ ll u=q.front(); q.pop_front(); if((double)(k[i])<lv(u,q.front())){ q.push_front(u); break; } } f[i]=f[q.front()]+k[i]*(n-q.front()); x[i]=i,y[i]=f[i]; while(q.size()>=2){ ll u=q.back(); q.pop_back(); if(lv(u,q.back())<lv(u,i)){ q.push_back(u); break; } } q.push_back(i); } write(f[n]); return 0; } ```