题解 P1725 【琪露诺】

· · 题解

------------ ### 思路： 发现可以用$dp_i$表示第$i$格的最大值，转移范围在$(i-R)$~$(i-L)$之间。 所以需要维护某一个固定长度的区间内的最大值。 ------------ ### 方法$1$： 单调队列： 用$q_i$表示队伍的编号，单调队列模板水一下： ```cpp #include<bits/stdc++.h> using namespace std; #define ll long long #define N 400005 #define rep(i,x,y) for(int i=x;i<=y;i++) int dp[N],a[N],n,q[N]; template<typename T> inline void read(T&x) { char ch=getchar(); x=0; bool f=0; for(; ch<'0'||ch>'9'; ch=getchar())if(ch=='-')f=1; for(; ch>='0'&&ch<='9'; x=(x<<1)+(x<<3)+(ch&15),ch=getchar()); if(f)x=-x; } template<typename T> inline void write(T x) { if(x<0)x=-x,putchar('-'); if(x>9)write(x/10); putchar(x%10|48); } template<typename T> inline void writeln(T x) { write(x),putchar('\n'); } int main(){ int L,R; cin>>n>>L>>R; for(int i=0;i<=n;i++)read(a[i]); memset(dp,128,sizeof(dp)); int head=1,tail=0,ans=-2e9; dp[0]=0; for(int i=L;i<=n+n;i++){ int l=max(0,i-R),r=max(0,i-L); while(q[head]<l&&head<=tail)head++; while(dp[q[tail]]<=dp[r]&&head<=tail)tail--; q[++tail]=r,dp[i]=dp[q[head]]+a[i]; ans=max(ans,dp[i]); } cout<<ans; return 0; } //BY CYN ``` 复杂度$O(N)

方法2：

我不会单调队列怎么办？

用分块维护区间最大值（带修改），块的大小取n^{\frac{1}{3}}较优。

在单点位置上修改，

查询时边角暴力，块内跳着查询。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 400005
#define rep(i,x,y) for(int i=x;i<=y;i++)
int dp[N],pre[N],add[N],a[N];
int bel[N],cnt,n,m;
template<typename T> inline void read(T&x) {
    char ch=getchar();
    x=0;
    bool f=0;
    for(; ch<'0'||ch>'9'; ch=getchar())if(ch=='-')f=1;
    for(; ch>='0'&&ch<='9'; x=(x<<1)+(x<<3)+(ch&15),ch=getchar());
    if(f)x=-x;
}
template<typename T> inline void write(T x) {
    if(x<0)x=-x,putchar('-');
    if(x>9)write(x/10);
    putchar(x%10|48);
}
template<typename T> inline void writeln(T x) {
    write(x),putchar('\n');
}
inline void Res(int x){
    pre[x]=-2e9;
    rep(i,(x-1)*cnt+1,min(cnt*x,n))pre[x]=max(pre[x],dp[i]);
}
inline void update(int p,int val){
    a[p]=val;
    Res(bel[p]);
}
inline int query(int l,int r){
    int ans=-2e9;
    rep(i,l,min(bel[l]*cnt,r))ans=max(ans,dp[i]);
    if(bel[l]!=bel[r]){
        rep(i,(bel[r]-1)*cnt+1,r)ans=max(ans,dp[i]);
    }
    rep(i,bel[l]+1,bel[r]-1)ans=max(ans,pre[i]);
    return ans;
}
int main(){
    int L,R;
    cin>>n>>L>>R;
    cnt=(int)pow(n,0.333);
    for(int i=0;i<=n;i++){
        read(a[i]);
    }
    for(int i=1;i<=n+n;i++)bel[i]=(i-1)/cnt+1;
    int ans=-2e9;
    memset(dp,128,sizeof(dp));
    memset(pre,128,sizeof(pre));
    dp[0]=0;
    update(0,0);
    for(int i=L;i<=n+n;i++){
        int l=max(0,i-R),r=max(0,i-L);
        int mx=query(l,r);
        //cout<<l<<' '<<r<<' '<<mx<<' '<<endl;
        dp[i]=mx+a[i];
        update(i,dp[i]);
        ans=max(ans,dp[i]);
    }//puts("");
    //for(int i=1;i<=n+n;i++)cout<<pre[i]<<' ';cout<<endl;
    cout<<ans;
    return 0;
} 
//BY CYN

耗时1000+ms

方法3：

同样的一个区间，可以用线段树或堆或Splay来维护，复杂度O(N logN)

方法4：

据说可以树状数组区间查询最大值？

复杂度O(Nlog^2N)