poj3017 Cut the Sequence[平衡树+单调队列优化]

方程$f_i=\min\{f_j+\max_{j+1\sim i}\}$。

本质上是决策点与区间最大值有一定关系，於是用单调队列来维护决策集合（而不是常规的），然后在决策集合中选取最小值。

然后觉得这题方法还是很重要的。没写平衡树，用优先队列（堆）来维护，单调队列维护最大值删除元素时用vis标记一下，取优先队列首的时候判断有没有被标记过，是的话就扔掉重复此动作。

然后最左端是特例，特殊对待就行了。具体还看上面↑。

2019.11.05 UPD：

什么嘛，DP优化学傻掉了，这个平衡树的优化根本不优秀好吗，如果$f$改成不单调的，然后有$\max,\min$两个一起出现，不就全部木大了吗。

观察一下，实际上单调队列（或者实际是栈）里面每一个元素表示这个数控制了这一段区间的最值（$q[i-1]+1\sim q[i]$）。那我显然可以直接把$f_j$塞到线段树的$j$里（基于序列的），然后控制区间最值的数对这段数区间加，然后插入新元素的时候单调栈弹栈，把栈顶这个元素控制的这个区间统一减去这个最值，最后统一使用新的元素，也就是区间加，同时在线段树里维护min就行了。

错误：很智障的把m数据类型定义为int。。结果查半天才发现是类型不对。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 using namespace std;

 typedef long long ll;

 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}

 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=+;const ll INF=1e13;

 struct komeiji_satori{

     int las,now;

     komeiji_satori(int x=,int y=):las(x),now(y){}

 };

 ll a[N],sum[N],f[N],m;//m!!!!long long !!!

 int q[N],vis[N];

 int n,L,l=,r=;

 priority_queue<komeiji_satori> minv;

 inline bool operator <(const komeiji_satori&A,const komeiji_satori&B){

     return f[A.las]+a[A.now]>f[B.las]+a[B.now];

 }

 inline ll getans(){

     while(!minv.empty()){

         int las=minv.top().las,now=minv.top().now;

         if(vis[now])minv.pop();

         else return f[las]+a[now];

     }

     return INF;

 }

 int main(){//freopen("test.in","r",stdin);freopen("tmp.out","w",stdout);

     read(n),read(m);

     for(register int i=;i<=n;++i){

         read(a[i]);sum[i]=a[i]+sum[i-];

         if(a[i]>m)return printf("-1\n"),;

     }

     for(register int i=;i<=n;++i){

         while(sum[i]-sum[L]>m)++L;

         while(l<=r&&a[q[r]]<=a[i])vis[q[r--]]=;

         q[++r]=i;

         while(l<=r&&q[l]<=L)vis[q[l++]]=;

         vis[q[l]]=;

         if(l<r)minv.push(komeiji_satori(q[r-],q[r]));//attention.

         f[i]=_min(getans(),f[L]+a[q[l]]);

     }

     printf("%lld\n",f[n]);

     return ;

 }

巴特西

poj3017 Cut the Sequence[平衡树+单调队列优化]

最新文章

热门文章