洛谷P5892 [IOI2014] holiday 假期

发现最优情况一定是一直向一个方向走或先走一段后再回来往回走一段。向左和向右是一样的，只需翻转就能转化为同一个问题了。

考虑枚举走的区间，设走完整个区间后的剩余天数为 (k)，那么对于该区间的最优答案一定是参观区间内权值前 (k) 大的城市，用主席树实现可以做到 (O(n^2 log n)) 的复杂度。

发现随着左端点的变大，其对应的最优的右端点一定是不降的，也就是其具有决策单调性。因为之前的最优的右端点的城市一定是参观的，所以将右端点移出区间是不优的。

像决策单调性的 (DP) 一样分治解决即可，复杂度为 (O(n log^2 n))。

#include<bits/stdc++.h>
#define maxn 100010
#define maxm 3000010
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
int n,s,d,cnt,tot;
ll ans;
int rt[maxn],ls[maxm],rs[maxm];
ll a[maxn],b[maxn],siz[maxm],sum[maxm];
void insert(int l,int r,int pos,int &cur)
{
    int x=++tot;
    ls[x]=ls[cur],rs[x]=rs[cur];
    siz[x]=siz[cur]+1,sum[x]=sum[cur]+b[pos],cur=x;
    if(l==r) return;
    if(pos<=mid) insert(l,mid,pos,ls[cur]);
    else insert(mid+1,r,pos,rs[cur]);
}
ll query(int l,int r,int k,int x,int y)
{
    if(k<=0) return 0;
    if(k>siz[y]-siz[x]) return sum[y]-sum[x];
    if(l==r) return b[l]*k;
    if(k<=siz[rs[y]]-siz[rs[x]]) return query(mid+1,r,k,rs[x],rs[y]);
    return query(l,mid,k-siz[rs[y]]+siz[rs[x]],ls[x],ls[y])+sum[rs[y]]-sum[rs[x]];
}
ll calc(int l,int r)
{
    return query(1,cnt,d-(2*(r-s)+s-l),rt[l-1],rt[r]);
}
void solve(int l,int r,int L,int R)
{
    if(l>r) return;
    if(L==R)
    {
        for(int i=l;i<=r;++i) ans=max(ans,calc(i,L));
        return;
    }
    ll pos=L,mx=calc(mid,L);
    for(int i=L+1;i<=R;++i)
    {
        ll v=calc(mid,i);
        if(v>mx) mx=v,pos=i;
    }
    ans=max(ans,mx),solve(l,mid-1,L,pos),solve(mid+1,r,pos,R);
}
void clear()
{
    for(int i=1;i<=n;++i) rt[i]=0;
    for(int i=1;i<=tot;++i) ls[i]=rs[i]=siz[i]=sum[i]=0;
    tot=0;
}
void work()
{
    clear();
    for(int i=1;i<=n;++i) rt[i]=rt[i-1],insert(1,cnt,a[i],rt[i]);
    for(int i=1;i<=s;++i) ans=max(ans,calc(i,s));
    solve(1,s-1,s+1,n);
}
int main()
{
    read(n),read(s),read(d),s++;
    for(int i=1;i<=n;++i) read(a[i]),b[i]=a[i];
    sort(b+1,b+n+1),cnt=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
    work(),s=n-s+1,reverse(a+1,a+n+1),work(),printf("%lld",ans);
    return 0;
}

洛谷P5892 [IOI2014] holiday 假期

相关推荐