简要题意
给你 (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})
设 (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;i0;j--){
mn=max(mn,h[j]);
if(sum[i]-sum[j-1]
首先，最后一个满足 (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
#define ls (i<>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=ql){
ret=min(ret,get(ql,qr,ls,l,mid));
}
if(mid sta;
int lft[100005];
signed main(){
cin>>n>>l;
for(int i=1;i>h[i]>>w[i];
sumw[i]=sumw[i-1]+w[i];
}
h[0]=INT_MAX;sta.push(0);
for(int i=1;ih[sta.top()]){
sta.pop();
}
lft[i]=sta.top();
sta.push(i);
}
sgt::build(1,1,n);
for(int i=1;i
Original: https://www.cnblogs.com/zheyuanxie/p/p1848.html
Author: xiezheyuan
Title: P1848 [USACO12OPEN]Bookshelf G
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604579/
转载文章受原作者版权保护。转载请注明原作者出处！