义乌中学暑假集训 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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇