题目描述

由于目前可供奶牛们使用的约会网站并没有给 Farmer John 留下深刻印象，他决定推出一个基于新匹配算法的奶牛交友网站，该算法可基于公牛和母牛间的共同兴趣对公牛和母牛进行匹配。

Bessie 在寻找情人节 Barn Dance 的合作伙伴时，决定试用这个网站。在注册账户之后，FJ 的算法为他给出了一个长度为 N（1≤N≤10^6） 的匹配列表，列表上每头公牛接受她舞蹈邀请的概率为 p （0<p<1）。

Bessie 决定向列表中的一个连续区间内的奶牛发送邀请，但Bessie希望恰好只有一个奶牛接受邀请。请帮助 Bessie 求出恰好只有一个奶牛接受邀请的最大概率是多少。

题解

一段的概率可以表示成

\((\prod_{l<=i<=r}1-p[i])*\sum_{l<=i<=r}\frac{p[i]}{1-p[i]}\)

设前面的为s1，后面的为s2

枚举l，加上r+1时更优当且仅当

\(s1*s2<s1*(1-p[r+1])*(s2+\frac{p[r+1]}{1-p[r+1]})\)

\(s1*s2<s1*s2*(1-p[r+1])+s1*p[r+1]\)$

\(s1*s2<s1*s2-s1*s2*p[r+1]+s1*p[r+1]\)

\(s2<1\)

因此可以把右端点单调

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define file
using namespace std;

double a[1000001],s1,s2,ans,s;
int n,i,j,k,l;

void Read(int &x) {x=0;char ch=getchar(); while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();}

int main()
{
	freopen("cowdate.in","r",stdin);
	#ifdef file
	freopen("cowdate.out","w",stdout);
	#endif
	
	Read(n);
	fo(i,1,n) Read(j),a[i]=1-1.0*j/1000000,ans=max(ans,1-a[i]);
	
	fo(i,1,n)
	{
		s1=a[i];s2=1;
		fo(j,i+1,min(i+100,n))
		s2=s2*a[j]+s1,s1*=a[j],s=s2-(j-i+1)*s1,ans=max(ans,s);
	}
	printf("%.0lf\n",ans*1000000);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}