自动搬运

查看原文

来自洛谷，原作者为

	w4p3r I think all our memories, and everything in it. . .can be nothing but the fiction we tell ourselves.

搬运于2025-08-24 22:08:36，当前版本为作者最后更新于2019-09-14 09:35:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

1.前言

做完这道题，我一看题解就懵了，这些都是什么神仙三分，神仙做法。

2.做法

我的做法也是决策单调性，但是我们要证明一下，这个东西为什么有决策单调性。

$l-r$这段区间的算出来的值是：

$\sum_{i=l}^{r}p_i \prod_{j=l,j!=i}^{r} {(1-p_j)}$

假设$S_l^r=\prod_{i=l}^{r}{(1-p_i)}$

则原式$=\sum_{i=l}^{r}\frac{p_i}{1-p_i}S_l^r=S_l^r\sum_{i=l}^{r}\frac{p_i}{1-p_i}$

为了方便，现在假设$a_i=1-p_i,b_i=\frac{p_i}{1-p_i}$

则$l-r$算出来的值为:$\prod_{i=l}^r a_i\sum_{i=l}^rb_i$

我们考虑把$r$变成$r+1$会发生什么

再次为了方便，假设$A=\prod_{i=l}^r a_i,B=\sum_{i=l}^rb_i$

则$r$变成$r+1$后，答案变成：

$(A*a_{r+1})(B+b_{r+1})$

$=A(a_{r+1}B+a_{r+1}b_{r+1})$

$=A(a_{r+1}B+p_{r+1})$(不知道为什么回去看看$a,b$的定义)

我们假设答案变大，康康会发生什么

即假设$a_{r+1}B+p_{r+1}>B$

根据$a$的定义，可以得到$(1-p_{r+1})B+p_{r+1}>B$

等式变形之后，可以得到$B<1$

$B<1????$

这样问题就变得十分简单了，对于每个$l$，你找到最远的$r$,使得$\sum_{i=l}^{r}b_i<1$即可

这当然可以二分,时间复杂度$O(nlogn)$

但是显然的，这个是具有单调性的，所以你可以直接用单调性做，时间复杂度$O(n)$

(因此其实主要原因不是答案决策有单调性（答案的确也有单调性），而是找到最远的r使b的和<1具有单调性，使得答案也有单调性)

3.代码

我写的是$O(n)$的单调性

#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define N 1000010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
double A=1,B;
int n,R=0;
double p[N],ans;
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();
	for(register int i=1;i<=n;i++)p[i]=read(),p[i]/=1e6,ans=max(ans,p[i]);
	//L左端点，R右端点 
	for(register int L=1;L<=n;L++)
	{
		while(R<n&&B<1){R++;B+=p[R]/(1-p[R]);A*=(1-p[R]);}//单调性 
		ans=max(ans,A*B);//统计答案 
		A/=(1-p[L]);B-=p[L]/(1-p[L]);//把L变成L+1 
	}
	printf("%d\n",int(ans*1e6));
	return 0;
}

（我10行头文件被说：很遗憾，您上传的题解【题解 P5242 【[USACO19FEB]Cow Dating】】因为【拒绝: 请勿在代码前添加超长预编译指令】未能通过审核。）了？？

如果认为我这篇题解对你有帮助的可以给我点一下赞qwq。如果有任何疑问，或者认为我的题解有什么问题的话，请务必私信我，感激不尽！我会努力把我的题解写得最好的!