简要题意
给你 \(N\) 本书 \((h_i,w_i)\)，你要将书分成任意段（顺序不能改变），使得每一段 \(j\) 中 \(\sum\limits_{i \in j} w_i \leq L\)，段 \(j\) 的代价为 \(\max\limits_{i \in j}{h_i}\)。你需要输出每一段的代价之和的最小值。
\(1 \leq N \leq 10^{5}\)
思路
朴素 DP 思路
设 \(f_i\) 为前 \(i\) 本书的代价和。则：
\[\begin{aligned} & W(i,j) = \sum_{k=i}^{j}{w_k} \\ & H(i,j) = \max_{k=i}^{j}{h_k} \\ & f_i = \min_{W(j,i) \leq L}{(f_{j-1} + H(j,i))} \end{aligned} \]解释：将 \([j,i]\) 中的书放在合并，然后成为一个新的段。
时间复杂度 \(O(n^3)\)。经过前缀和优化后 \(O(n^2)\)，无法通过本题。
代码如下：
for(int i=1;i<=n;i++){
dp[i]=0x7f7f7f7f7fll;
sum[i]=sum[i-1]+w[i];
}
for(int i=1;i<=n;i++){
mn=INT_MIN;
for(int j=i;j>0;j--){
mn=max(mn,h[j]);
if(sum[i]-sum[j-1]<=m){
dp[i]=min(dp[i],dp[j-1]+mn);
}
else{
break;
}
}
}
cout<<dp[n];
DP 优化
首先，最后一个满足 \(W(j,i) \leq l\) 的 \(j\) 是可以二分得出的（因为题目中 \(w\) 的前缀和是单调不降的）。我们姑且设其为 \(p_i\)，则：
\[f_i = \min_{p_i}^{i}{(f_{j-1} + H(j,i))} \]另外我们设 \(l_i\) 为左边第一个满足 \(h_j>h_i\) 的 \(j\)，即：
\[l_i = \max_{j=1}^{n}{(j \cdot [h_j > h_i])} \]那么如果 \(l_i \lt j \leq i\)，则 \(H(j,i)=h_i\)，只需要找到最小的 \(f_{j-1}\)即可。至于其他的，就用继承下来的。这是正确的。
这道题没法 ODT，老老实实的线段树。
代码
耗时最长的一道题祭
#include <bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
#define int long long
using namespace std;
int f,n,l,h[100005],w[100005],sumw[100005];
namespace sgt{
struct node{
int f,fh,tag;
} t[400005];
void pushup(int i){
t[i].f=min(t[ls].f,t[rs].f);
t[i].fh=min(t[ls].fh,t[rs].fh);
}
void pushdown(int i){
if(t[i].tag!=(-1e9)){
t[ls].fh=t[ls].f+t[i].tag;
t[rs].fh=t[rs].f+t[i].tag;
t[ls].tag=t[i].tag;
t[rs].tag=t[i].tag;
t[i].tag=(-1e9);
}
}
void build(int i,int l,int r){
if(l==r){
t[i].fh=LLONG_MAX;
t[i].f=t[i].fh;
t[i].tag=(-1e9);
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(i);
}
void init(int p,int i,int l,int r){
if(l==r){
t[i].fh=LLONG_MAX;
t[i].f=f;
return;
}
pushdown(i);
if(p<=mid){
init(p,ls,l,mid);
}
else{
init(p,rs,mid+1,r);
}
pushup(i);
}
void assign(int ql,int qr,int k,int i,int l,int r){
if(ql<=l&&r<=qr){
t[i].fh=t[i].f+k;
t[i].tag=k;
return;
}
pushdown(i);
if(ql<=mid){
assign(ql,qr,k,ls,l,mid);
}
if(mid<qr){
assign(ql,qr,k,rs,mid+1,r);
}
pushup(i);
}
int get(int ql,int qr,int i,int l,int r){
if(ql<=l&&r<=qr){
return t[i].fh;
}
pushdown(i);
int ret=LLONG_MAX;
if(mid>=ql){
ret=min(ret,get(ql,qr,ls,l,mid));
}
if(mid<qr){
ret=min(ret,get(ql,qr,rs,mid+1,r));
}
return ret;
}
}
stack<int> sta;
int lft[100005];
signed main(){
cin>>n>>l;
for(int i=1;i<=n;i++){
cin>>h[i]>>w[i];
sumw[i]=sumw[i-1]+w[i];
}
h[0]=INT_MAX;sta.push(0);
for(int i=1;i<=n;i++){
while(!sta.empty()&&h[i]>h[sta.top()]){
sta.pop();
}
lft[i]=sta.top();
sta.push(i);
}
sgt::build(1,1,n);
for(int i=1;i<=n;i++){
// cout<<"INIT "<<i<<'\n';
sgt::init(i,1,1,n);
// cout<<"ASSIGN "<<i<<'\n';
sgt::assign(lft[i]+1,i,h[i],1,1,n);
// cout<<"LOWERBOUND "<<i<<'\n';
int ll = lower_bound(sumw,sumw+i+1,sumw[i]-l)-sumw;
if(ll<i){
f=sgt::get(ll+1,i,1,1,n);
}
}
cout<<f;
}