[AGC044E] Random Pawn

AGC044E
首先列出基本的转移式,设 \(f_i\) 为从 i 出发期望的最大收益。
则 \(f_i=\max(a_i,\frac{f_{i-1}+f_{i+1}}{2}-b_i)\)。
不难看出 a 最大的点的期望值一定是 a,因为不可能花费 b 去获得 a 更小的值。
把这个点记为 \(a_0\)。
考虑如何去掉常数。
我们设 \(g_i=f_i+d_i\),则原式变为 \(g_i=(\max{a_i+d_i,\frac{g_{i-1}+g_{i+1}}{2}}-\frac{d_{i-1}+d_{i+1}}{2}-b_i+d_i)\)
那么 d 就可以递推出来。
设 \(c_i=a_i+d_i\)
则原式变为 \(g_i=\max(c_i,\frac{g_{i-1}+g_{i+1}}{2})\)
\(g_0=c_0,g_n=c_n\)
然后就比较精彩了,我们发现 g 的值可以表示为相邻两个点的中点的 y 值。
先不考虑 c 我们可以发现 g 是单减的直线。
加上 c 后,不难发现有贡献的 c 是一个上凸壳,因为 \(\frac{c_{i-1}+c_{i+1}}{2}>c_{i}\)
又因为上面提到的中点,新的 g 值就是这个凸壳。
直接维护即可。
code:

#include<cstdio>
#include<iostream>
using namespace std;
#define db double
const int MAXN=2e5+5;
const db eps=1e-12;
db xj(db A,db B,db C,db D){
;	return A*D-B*C;	
}
int n,q[MAXN],wz,ta,a1[MAXN];
db a[MAXN],b[MAXN],d[MAXN],dp[MAXN],c[MAXN],ma,Ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lf",&a[i]);
		if(a[i]>ma){
			ma=a[i];wz=i;
		}
	}
	for(int i=wz;i<=n;i++){
		a1[i-wz]=i;
	}
	for(int i=1;i<wz;i++){
		a1[n-wz+i]=i;
	}
	a1[n]=a1[0];
	for(int i=1;i<=n;i++) scanf("%lf",&b[i]);
	d[0]=0;d[1]=0;
	for(int i=1;i<n;i++){
		d[i+1]=2*(d[i]-b[a1[i]])-d[i-1];
	}
	q[0]=0;
	for(int i=0;i<=n;i++) c[i]=a[a1[i]]+d[i];
	for(int i=1;i<=n;i++){
		while(ta&&-xj(i-q[ta],c[i]-c[q[ta]],i-q[ta-1],c[i]-c[q[ta-1]])>eps) ta--;
		q[++ta]=i;
	}
	for(int i=0;i<ta;i++){
		db k=(c[q[i+1]]-c[q[i]])/(q[i+1]-q[i]),b=c[q[i]]-k*q[i];
		for(int j=q[i];j<q[i+1];j++) dp[j]=k*j+b;
	}
	for(int i=0;i<n;i++) Ans+=dp[i]-d[i];
	printf("%.10lf",Ans/n);
	return 0;
}