题解：P11333 [NOISG 2020 Finals] Discharging
Fenki_lo
·
·
题解
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。求最小费用。
## 思路
设 $f_{i}$ 表示前 $i$ 个顾客的最小充电时间。
考虑“延后贡献”。
设 $f_i$ 表示前 $i$ 个的最小往后总贡献。
$$\begin{aligned}
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;
}
```