题目描述
给定一个长度为 N 的序列 A ,要求把该序列分成若干段,在满足“每段中所有数的和”不超过M的前提下,让“每段中所有数的最大值”之和最小。
试计算这个最小值。
样例
输入样例:
8 17
2 2 2 8 1 8 2 1
输出样例:
12
算法1
(单调队列+set) $O(nlogn)$
不是太懂....至于暴力扫单调队列,本着原则下不去手去写…
所以看下一个算法吧!
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(线段树+单调栈) $O(nlogn)$
题解中没人用线段树吗?.....那我来一发吧!
其实这道题让我们头疼的就是随着i的推进,以前的决策答案可能会发生变化,所以不能简单用普通的单调队列来做,那我们用线段树暴力修改怎么样?(这也太暴力了吧)
我们线段树的每个叶子节点记录答案,即l==r==2的一个叶子结点表示在当前i的情况之下
的f[2]+max(a[2+1]到a[i])的值,然后用线段树维护最小值,这样我们转移就很好转移
我们用pos记录对于i来说最小的j使得a[j]+…+a[i]<=m.
那f[i]=ask(1,pos-1,i-1)即可,注意这里是pos-1,因为决策pos-1,用到的值是pos到i的最大值.
之后我们考虑怎么维护这个线段树…
我们考虑一个事情,对于一个决策j来说随着i的推进,它的max(a[j+1到a[i])只会递增
那我们想到单调栈,之后的个图就行了:
对于一个决策j,我们考虑q[j-1]+1到q[j]的元素想象一下他们到i的最大值是谁,
发现了吗?一定是a[q[j]]因为之后的一定比a[q[j]]小,所以我们就知道单调栈一个点是有管辖范围即那个范围的最大值都是a[q[j]]…那当q[j]弹出栈是会怎么样?
表示后面随着i的推进,有比a[q[j]]更大的数,那它所管辖的范围的最大值就都变成新来的数..
这样就可以暴力修改了,由于栈的性质,每个元素只进一次,只出一次,所以最多有n次修改.
复杂度O(nlogn).
细节还是蛮多的.建议码力不行的,看完我的代码后自己再打一遍,更易理解思路.
PS:(好题推荐)
附上洛谷的原题,第二遍可以交这个题,状态一模一样....
P1848 [USACO12OPEN]Bookshelf G
再附一道类似的题目,我朋友出的,希望有同感的朋友做一下…
( 魁拔 )(一起支持国漫吧!)
还有我出的题目,也是我的童年,是一道挺好的题(与DP毫无关系).
高高飞起来-纪念那曾经的<星游记>…
觉得好的话就支持一下吧,打字真的很累的…
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
const ll INF=1e18;
ll n,m,a[N],q[N],top,f[N];
struct Tree
{
int l,r;
ll data,lazy;
#define l(x) t[x].l
#define r(x) t[x].r
#define data(x) t[x].data
#define lazy(x) t[x].lazy
}t[N<<2];
inline ll read()
{
ll x=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*ff;
}
inline void push(int p)
{
if(lazy(p))
{
data(p<<1)+=lazy(p);
data(p<<1|1)+=lazy(p);
lazy(p<<1)+=lazy(p);
lazy(p<<1|1)+=lazy(p);
lazy(p)=0;
}
}
inline void build(int p,int l,int r)
{
l(p)=l,r(p)=r;
if(l==r) return;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
inline void change(int p,int l,int r,ll k)
{
if(l<=l(p)&&r>=r(p))
{
data(p)+=k;
lazy(p)+=k;
return;
}
push(p);
int mid=l(p)+r(p)>>1;
if(l<=mid) change(p<<1,l,r,k);
if(r>=mid+1) change(p<<1|1,l,r,k);
data(p)=min(data(p<<1),data(p<<1|1));
}
inline ll ask(int p,int l,int r)
{
if(l<=l(p)&&r>=r(p)) return data(p);
push(p);
int mid=l(p)+r(p)>>1;
ll ans=INF;
if(l<=mid) ans=min(ans,ask(p<<1,l,r));
if(r>=mid+1) ans=min(ans,ask(p<<1|1,l,r));
return ans;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i) a[i]=read();
build(1,0,n);
ll ans=0,pos=1;
for(int i=1;i<=n;++i)
{
ans+=a[i];
while(ans>m) ans-=a[pos],pos++;
change(1,q[top],q[top],a[i]);
while(top&&a[i]>a[q[top]])
{
change(1,q[top-1],q[top]-1,a[i]-a[q[top]]);
top--;
}
q[++top]=i;
f[i]=ask(1,pos-1,i-1);
change(1,i,i,f[i]);
}
printf("%lld",f[n]);
return 0;
}
orz
Orz