首先肯定是向一边走一段（不走也行），然后回到原点，然后再向另一边走
算四个数组，分别表示向左还是向右，回还是不回，耗费i的时间最多游览的景点数
假如是向左走不回来（其他同理），我们可以枚举向左走到的端点，然后在这段区间中选择剩下时间数目的前k大值，主席树做到logn
朴素是O(T*n)的，但是可以发现有决策单调性，时间增加，走到的端点不会往回
但是值得注意的是，并不是说往前拓展就一定会更优，可能是走几步才会到达更优的决策点，这意味着不能够直接O(n)扫
用类似整体二分的思想分治，二分时间，然后枚举决策点区间找最优，根据当前决策点依单调性保证去除没用的点就好
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const int maxn=310000; int a[maxn],lslen;LL ls[maxn]; struct trnode { int lc,rc,c;LL s; }tr[maxn*8];int trlen,rt[maxn]; int maketree(int now,int l,int r,int p) { if(now==0) { now=++trlen; tr[now].lc=tr[now].rc=0; tr[now].c=0; } tr[now].c++; tr[now].s+=ls[p]; if(l<r) { int mid=(l+r)/2; if(p<=mid)tr[now].lc=maketree(tr[now].lc,l,mid,p); else tr[now].rc=maketree(tr[now].rc,mid+1,r,p); } return now; } int merge(int x,int y) { if(x==0||y==0)return x+y; tr[x].c+=tr[y].c; tr[x].s+=tr[y].s; tr[x].lc=merge(tr[x].lc,tr[y].lc); tr[x].rc=merge(tr[x].rc,tr[y].rc); return x; } LL getksum(int x,int y,int l,int r,int k) { int c=tr[y].c-tr[x].c; if(c<=k)return tr[y].s-tr[x].s; if(l==r)return LL(k)*ls[l]; int mid=(l+r)/2; c=tr[tr[y].rc].c-tr[tr[x].rc].c; if(c==k)return tr[tr[y].rc].s-tr[tr[x].rc].s; else if(k<c)return getksum(tr[x].rc,tr[y].rc,mid+1,r,k); else return tr[tr[y].rc].s-tr[tr[x].rc].s+getksum(tr[x].lc,tr[y].lc,l,mid,k-c); } LL qwer(int x,int y,int k) { if(x>y)swap(x,y); return getksum(rt[x-1],rt[y],1,lslen,k); } //-------------------------------------getksum------------------------------------------------ int ST; LL calc(int t,int p,int w) { if(abs(ST-p)*w>=t)return 0; return qwer(p,ST,t-abs(ST-p)*w); } LL f[4][maxn];int w; void solve(int l,int r,int st,int ed) { if(l>r)return ; int mid=(l+r)/2,u; f[w][mid]=calc(mid,st,w%2+1),u=st; for(int p=st+1;p<=ed;p++) { LL d=calc(mid,p,w%2+1); if(f[w][mid]<d)f[w][mid]=d,u=p; } if(w<=1) solve(l,mid-1,u,ed), solve(mid+1,r,st,u); else solve(l,mid-1,st,u), solve(mid+1,r,u,ed); } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int n,m; scanf("%d%d%d",&n,&ST,&m);ST++; for(int i=1;i<=n;i++) scanf("%d",&a[i]),ls[++lslen]=a[i]; sort(ls+1,ls+lslen+1); lslen=unique(ls+1,ls+lslen+1)-ls-1; for(int i=1;i<=n;i++) a[i]=lower_bound(ls+1,ls+lslen+1,a[i])-ls; for(int i=1;i<=n;i++) { rt[i]=maketree(rt[i],1,lslen,a[i]); rt[i]=merge(rt[i],rt[i-1]); } w=0,solve(1,m,1,ST); w=1,solve(1,m,1,ST); ST++; if(ST!=n+1) { w=2,solve(1,m-1,ST,n); w=3,solve(1,m-2,ST,n); } LL ans=0; for(int i=0;i<=m;i++) ans=max(ans,f[0][i]+f[3][max(0,m-i-2)]), ans=max(ans,f[1][i]+f[2][max(0,m-i-1)]); printf("%lld ",ans); return 0; }