题意:
给出X轴上的n个点的坐标,每一个点的位置都有一个权值,有正有负,你可以移动X步,问可以获得的最大权值和是多少。
思路:
这里提供一个比较容易理解的做法,比赛时写bug一直没调出来,首先我们肯定要找到最后一个小于等于0的位置t,然后用一个辅助数组b记录从t开始到1和从t+1到n的权值累加和,然后分成两种情况讨论,第一种是只在X轴正方向上的最大值和只在X负方向的最大值,第二种是X轴正方向和负方向都有的情况;第一种情况我们在累加的时候直接判断即可(注意此时要判断能否到达该位置)。
比较复杂的是第二种情况,我们可以先假设从0出发到负方向的位置,再从负方向的位置到正坐标的位置,对于每一个负方向的位置我们直接可以通过B数组直接求得,主要是求在X轴正方向上可以获得的最大值,所以我们需要先求得回到0位置时我们还剩多少步数,然后二分我们可以最远到达正方向得哪一个位置,而在X轴正方向上我们可以获得的最大权值就是正方向起始和最远位置之间的权值累加和的最大值,这个地方可以用线段树或者ST表进行求得,然后我们再对X正方向也做一遍这样的思路,就可以解决第二种情况了。需要注意的是如果在X轴正负方向累加和均<=0时,我们需要特判一下-1和1的位置,因为我们不能不移动。
代码如下:
比较啰嗦,有些可以不写的,就不改了:
#include<bits/stdc++.h> #define LL long long #define all(x) (x).begin(),(x).end() #define le(x) ((int)(x).size()) #define pii pair<int,int> #define PII pair<LL,LL> #define mp make_pair #define pb push_back #define fi first #define se second #define db printf("Here!\n"); using namespace std; const double eps=1e-8; const double Pi=4.0*atan(1.0); const LL inf=1e18+10; const int N=5e5+5; const int M=2e6+5; const int mod=1e9+7; //mt19937 rnd(time(0)),shuffle(a+1,a+1+n,rnd); LL n,m,k,t,T,len,op,x,y,z,ind; LL a[N],p[N],b[N],ans=-inf,c[N],d[N]; vector<PII >v[3]; struct node{ int l,r; int mx; }q[N*4]; void change(int now){ q[now].mx=max(q[now<<1].mx,q[now<<1|1].mx); } void build(int now,int L,int R){ q[now].l=L;q[now].r=R; if(L==R){ q[now].mx=d[L]; return; } int mid=L+R>>1; build(now<<1,L,mid); build(now<<1|1,mid+1,R); change(now); } int qmx(int now,int L,int R){ if(q[now].l>=L&&q[now].r<=R){ return q[now].mx; } int mid=q[now].l+q[now].r>>1; int res=0; if(mid>=L)res=max(res,qmx(now<<1,L,R)); if(R>mid)res=max(res,qmx(now<<1|1,L,R)); return res; } map<int,int>pp; void solve(){ scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&p[i]); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); for(int i=1;i<=n;i++){ if(p[i]==-1)pp[-1]=a[i]; if(p[i]==1)pp[1]=a[i]; } for(int i=1;i<=n;i++){ if(p[i]>0){ t=i-1;break; } t=i; } for(int i=t;i>=1;i--){ x+=a[i]; b[i]=x; } for(int i=t+1;i<=n;i++){ y+=a[i]; b[i]=y; } x=y=0; for(int i=1;i<=n;i++){ if(b[i]>0){ if(i<=t&&-p[i]<=m)x++,ans=max(ans,b[i]); else if(i>t&&p[i]<=m)y++,ans=max(ans,b[i]); }else if(abs(p[i])<=m)ans=max(ans,b[i]);//增加了一个被评论区大佬hack点 } if(!x&&!y){ if(pp.count(-1)&&pp.count(1)){ ans=max(ans,1LL*max(pp[-1],pp[1])); }else ans=0; }else if(x&&y){ for(int i=t+1;i<=n;i++){ c[++T]=p[i]; d[T]=a[i]+d[T-1]; } build(1,1,T); for(int i=1;i<=t;i++){//先假设先去负方向 if(b[i]<=0||-p[i]>m)continue; LL now=m+2*p[i]; LL mx=0; z=lower_bound(c+1,c+1+T,now)-c; if(z>T)z=T; else if(c[z]>now)z--; if(z>=1)mx=qmx(1,1,z); if(mx>0){ ans=max(ans,b[i]+mx); } } T=0; for(int i=t;i>=1;i--){ c[++T]=-p[i]; d[T]=a[i]+d[T-1]; } build(1,1,T); for(int i=t+1;i<=n;i++){//再假设先去正方向 if(b[i]<=0||p[i]>m)continue; LL now=m-2*p[i]; LL mx=0; z=lower_bound(c+1,c+1+T,now)-c; if(z>T)z=T; else if(c[z]>now)z--; if(z>=1)mx=qmx(1,1,z); if(mx>0){ ans=max(ans,b[i]+mx); } } } printf("%lld\n",ans); } int main(){ //int o;scanf("%d",&o); //while(o--){ solve(); //} return 0; } /* 8 16 -18 -8 -2 1 3 8 10 20 20 -2 12 -5 9 1 -2 20 ans=17 10 60 -29 -18 -7 -5 -1 3 8 14 20 27 23 -11 8 -5 2 -5 8 14 -12 20 ans=34 */