Help needed in slope trick technique

Revision en1, by LCJLY, 2023-02-08 17:07:31

Hi everyone, I'm trying to learn a technique called the slope trick. I have read through several blogs on slope trick e.g https://codeforces.com/blog/entry/77298 and https://codeforces.com/blog/entry/47821. I went on to look at the problem "Sonya and Problem Wihtout A level". However I still couldn't understand how the slope trick work, I know that 2 slop-trickable function can be merged, but I still dunno what is the purpose of knowing that it can be merged and which point are we finding in the graph of the function.

cin>>n;
rep(x,1,n+1) cin>>arr[x];
rep(x,1,n+1) arr[x]-=x;

multiset<int,greater<int> > B={-(int)1e3};
int ans=0;

rep(x,1,n+1){
    if (*B.begin()<arr[x]){
        B.insert(arr[x]);
    }
    else{
        B.insert(arr[x]);
        B.insert(arr[x]);
        ans+=*B.begin()-arr[x];
        B.erase(B.begin());
    }
}

I have a few questions in mind and wanted to ask regarding the above code. 1) what does the multiset store? 2) why does it have to initialize with a large negative value first 3) why do we insert arr[x] twice in the else statement 4) why do we have two cases either <arr[x] or >arr[x]

Really appreciate if you can answer some of my doubts thanks

Tags dp, slope trick

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English LCJLY 2023-02-08 17:07:31 1276 Initial revision (published)