首页 > 代码库 > bzoj3521: [Poi2014]Salad Bar
bzoj3521: [Poi2014]Salad Bar
Description
有一个长度为n的字符串，每一位只会是p或j。你需要取出一个子串S（从左到右或从右到左一个一个取出），使得不管是从左往右还是从右往左取，都保证每时每刻已取出的p的个数不小于j的个数。你需要最大化|S|。
Input
第一行一个数n，第二行一个长度n的字符串。
Output
S的最大长度。
单调栈预处理出每个左端点向右延伸的最右位置和每个右端点向左延伸的最左位置，然后随便用数据结构维护一下就行了
#include<cstdio>int n,v[1000007],l[1000007],r[1000007],ss[1000007],sp=0,ans=0;char s[1000007];int mx[1000007],es[1000007],enx[1000007],e0[1000007],ep=2;int tr[2097152];void maxs(int&a,int b){if(a<b)a=b;}int main(){ scanf("%d%s",&n,s+1); for(int i=1;i<=n;++i)v[i]=v[i-1]+(s[i]==‘p‘?1:-1); for(int i=0;i<=n;++i){ while(sp&&v[ss[sp]]>v[i])r[ss[sp--]]=i-1; ss[++sp]=i; } while(sp)r[ss[sp--]]=n; for(int i=n;i;--i){ while(sp&&v[ss[sp]]<v[i])l[ss[sp--]]=i+1; ss[++sp]=i; } while(sp)l[ss[sp--]]=0; for(int i=0;i<=n;++i){ es[ep]=i;enx[ep]=e0[l[i]];e0[l[i]]=ep++; } for(int i=0;i<=n;++i){ for(int e=e0[i];e;e=enx[e]){ int u=es[e]; for(int w=u+1048577;w;w>>=1)maxs(tr[w],u); } int v=0; for(int l=i+1048576,r=::r[i]+1048578;l^r^1;l>>=1,r>>=1){ if(~l&1)maxs(v,tr[l^1]); if(r&1)maxs(v,tr[r^1]); } maxs(ans,v-i); } printf("%d",ans); return 0;}
bzoj3521: [Poi2014]Salad Bar
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。