思路:

首先分数规划是显然的.

其次就是要求长度必须为偶数,我们可以分成两种情况讨论也可以解决.

然后对于每一次二分,我们维护一个前缀和,那么以当前位置为结尾的最大权值和所对应的开头位置的前缀和我们利用一个单调队列维护即可.

关键是输出答案时要输出一个分数或整数!这个坑死爹了.

惨不忍睹地尝试了无数种方法之后.接近崩溃.(尤其是枚举分母一点都不靠谱啊啊啊啊啊啊啊)

终于想到了一种方法,在二分的时候顺便更新答案,最后直接输出.然后就这样水过去了.

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
 
typedef long double f2;
typedef long long LL;
 
#define N 100010
int n,l,r,a[N<<1],b[N],q[N],fr,ta;
 
f2 sum[N];LL realsum[N];
 
LL gcd(LL a,LL b){return(!b)?a:gcd(b,a%b);}
 
struct Ans{
    LL x,y;
    Ans(){}
    Ans(LL _x,LL _y):x(_x),y(_y){}
    bool operator<(const Ans&B)const{return x*B.y>y*B.x;}
};
 
inline void upd(Ans&t,int l,int r){
    Ans tmp=Ans(realsum[r]-realsum[l-1],2*(r-l+1));
    if(tmp<t)t=tmp;
}
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    //freopen("me.out","w",stdout);
#endif
    scanf("%d%d%d",&n,&l,&r);if(l<1)l=1;if(r>n)r=n;
    register int i,j;for(i=1;i<=n;++i)scanf("%d",&a[i]);for(i=n+1;i<=2*n;++i)a[i]=a[i-n];
     
    l=l%2==0?l:l+1,l>>=1;
    r=r%2==0?r:r-1,r>>=1;
     
    f2 L,R,mid,res=0;
    Ans sav(0,1);
     
    //solve1
    for(i=1;i<=n;++i)b[i]=a[2*i-1]+a[2*i],realsum[i]=realsum[i-1]+b[i];
     
    for(L=0,R=1e9;R-L>1e-10;){
        mid=(L+R)/2;
         
        for(i=1;i<=n;++i)sum[i]=sum[i-1]+b[i]-2*mid;
         
        f2 Max=sum[l];upd(sav,1,l);
        for(fr=ta=0,i=l+1;i<=n;++i){
            if(i<=r)Max=max(Max,sum[i]),upd(sav,1,i);
            while(fr^ta&&sum[q[ta-1]]>sum[i-l])--ta;q[ta++]=i-l;
            while(fr^ta&&q[fr]<i-r)++fr;if(fr^ta)Max=max(Max,sum[i]-sum[q[fr]]),upd(sav,q[fr]+1,i);
        }
         
        if(Max>=0)L=mid;else R=mid;
    }res=max(res,L);
     
    //solve2
    for(i=1;i<n;++i)b[i]=a[2*i]+a[2*i+1];b[n]=a[2*n]+a[1];
    for(i=1;i<=n;++i)realsum[i]=realsum[i-1]+b[i];
     
    for(L=0,R=1e9;R-L>1e-10;){
        mid=(L+R)/2;
         
        for(i=1;i<=n;++i)sum[i]=sum[i-1]+b[i]-2*mid;
         
        f2 Max=sum[l];upd(sav,1,l);
        for(fr=ta=0,i=l+1;i<=n;++i){
            if(i<=r)Max=max(Max,sum[i]),upd(sav,1,i);
            while(fr^ta&&sum[q[ta-1]]>sum[i-l])--ta;q[ta++]=i-l;
            while(fr^ta&&q[fr]<i-r)++fr;if(fr^ta)Max=max(Max,sum[i]-sum[q[fr]]),upd(sav,q[fr]+1,i);
        }
     
        if(Max>=0)L=mid;else R=mid;
    }res=max(res,L);
     
     
    LL ansx=sav.x,ansy=sav.y,Gcd=gcd(ansx,ansy);ansx/=Gcd,ansy/=Gcd;
#ifndef ONLINE_JUDGE
    if(ansy==1)printf("%I64d",ansx);else printf("%I64d/%I64d",ansx,ansy);
#else
    if(ansy==1)printf("%lld",ansx);else printf("%lld/%lld",ansx,ansy);
#endif
     
    return 0;
}

思路:

一开始是用的线段树优化dp,具体的就不说了.

我一开始觉得有的需要+1,有的不需要加,单调队列没办法做.

不过有一条性质,就是如果两条决策,其中一个的步数已经比另一个决策少,那么我们选择这个决策是一定不劣于另一个决策的.

否则若步数相同,我们当然选择保留高度较高的那个决策.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc())&&c!='-');bool sig=c=='-';
        x=sig?0:c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
        if(sig)x=-x;
    }
}
#define N 1000010
int h[N];
int q[N],fr,ta,f[N];
int main(){
	int n;Fio::Get(n);register int i,j;for(i=1;i<=n;++i)Fio::Get(h[i]);
	int Q;Fio::Get(Q);int lim;
	while(Q--){
		 Fio::Get(lim);
		 fr=ta=0;q[ta++]=1;f[1]=0;
		 for(i=2;i<=n;++i){
		 	while(fr^ta&&i>q[fr]+lim)++fr;f[i]=f[q[fr]]+(h[q[fr]]<=h[i]);
		 	while(fr^ta&&((f[i]<f[q[ta-1]])||(f[i]==f[q[ta-1]]&&h[i]>h[q[ta-1]])))--ta;
		 	q[ta++]=i;
		 }
		 printf("%d\n",f[n]);
	}return 0;
}