义乌中学暑假集训 2021.07.15 D

白云在白兔的城市，打算在这里住 $n$ 天，这 $n$ 天，白云计划找白兔订购水。

白云给出了接下来的 $n$​ 天，每天的需水量，第 $i$​ 天为 $D_i$ 升。

白兔给出了接下来的 $n$ 天，每天水的价格，第 $i$ 天为 $P_i$ 元每升。

白云的小区有一个共用水壶，最大容量为 $V$ 升，初始为空。 接下来每天，白云可以进行如下操作：

1. 把水壶中的水使用掉
2. 向白兔购买若干水，并放入水壶中
3. 向白兔购买若干水，并使用

任何时候水壶中的水不能超过 $V$ 升，而且每升水每在水壶中存放一天，需要付出 $m$ 元

白兔为了难为白云，决定在某些天进行破坏操作，即选择一个子序列 $b_1,…,b_t$，在这序列中的每一天，它会在当天早上把前一天储存的水放掉。第 $i$ 天有一个破坏难度 $val_i$，白兔为了挑战自己，决定让自己进行破坏操作的 $val$ 是严格单调递增。它会找一个破坏天数最多的方案，在保证破坏次数最多的前提下，使得破坏序列的字典序最小。

白云已经知道了白兔的想法，并且获取了这个破坏难度，所以它已经能计算出白兔会在哪些日子进行破坏。

那么白云想知道，在此基础上，白云要度过接下来 $n$ 天的最小总花费。

$m,p_i\leq 1000,n\leq 10^6,d_i,V\leq 10^7,val\leq 10^9$

Sol

首先可以求出字典序最小的最长上升子序列 $\mathcal O(n\log n)$。

然后对于一组最优解，如果第 $i$ 天买了水并保存在水壶里，那么 $p_i$ 一定是单增的。

所以直接维护一个单调队列，由于容量限制打一个全局标记即可。

#include<bits/stdc++.h>
#define I inline
#define W while
#define RI register int 
#define Cn const
#define CI Cn int& 
#define gc getchar
#define pc putchar
#define LL long long
using namespace std;
I void read(int& x){RI f=1;char c=gc();x=0;W(!('0'<=c&&c<='9')) f=c^'-'?f:-1,c=gc();W('0'<=c&&c<='9') x=x*10+(c-'0'),c=gc();x*=f;}
I void write(LL x){x<0&&(pc('-'),x=-x),x>=10&&(write(x/10),0),pc(x%10+'0');}
Cn int N=1e6+10;
int n,m,V,a[N],d[N],p[N],stk[N],top,dp[N],Mx,Ans[N],v[N],q[N],w[N],h,t;
LL ans;
vector<pair<int,int> > vis[N];
I void LIS(){
    RI i,j;for(stk[top=1]=a[1],Mx=1,dp[1]=1,i=2;i<=n;i++) if(a[i]>stk[top]) stk[++top]=a[i],dp[i]=top,Mx=max(Mx,top);
    else{RI t=lower_bound(stk+1,stk+top+1,a[i])-stk;dp[i]=t,stk[t]=a[i];}
    for(i=1;i<=n;i++) vis[dp[i]].push_back(make_pair(i,a[i]));
    for(Ans[Mx]=vis[Mx][0].first,i=Mx-1;i>=1;i--){
        RI r=vis[i].size();Ans[i]=2e9;
        for(j=0;j<r;j++) if(vis[i][j].second<a[Ans[i+1]]&&vis[i][j].first<Ans[i]) Ans[i]=vis[i][j].first;
    }for(i=1;i<=Mx;i++) v[Ans[i]]=1;
}
int main(){
    RI i,nd,tg=0;for(read(n),read(m),read(V),i=1;i<=n;i++) read(a[i]);
    for(i=1;i<=n;i++) read(d[i]);for(i=1;i<=n;i++) read(p[i]);
    LIS();for(h=1,t=0,i=1;i<=n;i++){
        if(v[i]) h=t+1;
        W(h<=t&&p[i]-(i-1)*m<=p[q[t]]) t--;
        nd=d[i];W(h<=t) if(nd<w[q[h]]-tg){ans+=1LL*(p[q[h]]+(i-1)*m)*nd,tg+=nd,nd=0;break ;}
        else ans+=1LL*(p[q[h]]+(i-1)*m)*(w[q[h]]-tg),nd-=w[q[h]]-tg,tg=w[q[h++]];
        ans+=1LL*nd*p[i],q[++t]=i,w[i]=V+tg,p[i]-=(i-1)*m;
    }return write(ans),0;
}