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。如果有任何疑问，或者认为我的题解有什么问题的话，请务必私信我，感激不尽！我会努力把我的题解写得最好的!

思路：

首先要明确，在一段左端点为 $l$，右端点为 $r$ 的区间内仅被一头奶牛选中的概率是 $\sum _ {i = l}^r p_i\prod_{j = l, j \neq i}^r (1 - p_j)$。

变式得到：$\sum _ {i = l}^r \dfrac{p_i}{1-p_i}\prod_{j = l}^r (1 - p_j)$。

设置两个决策点 $j_2$ 和 $j_1$。假设 $j_2$ 优于 $j_1$ 且 $j_2 > j_1$。设 $s_i = \sum _ {j = 1} ^ i \dfrac{p_j}{1-p_j}$，$m_i = \prod_{j = 1} ^ i (1 - p_j)$。

于是可得不等式：$\dfrac{m_i}{m_{j_2}}(s_i - s_{j_2}) > \dfrac{m_i}{m_{j_1}}(s_i - s_{j_1})$。

变式得 $s_i\dfrac{m_i}{m_{j_2}}-\dfrac{m_is_{j_2}}{m_{j_2}} > s_i\dfrac{m_i}{m_{j_1}}-\dfrac{m_is_{j_1}}{m_{j_1}}$。

$s_i(\dfrac{m_i}{m_{j_2}} - \dfrac{m_i}{m_{j_1}}) > \dfrac{m_is_{j_2}}{m_{j_2}} - \dfrac{m_is_{j_1}}{m_{j_1}}$。

$s_i>\dfrac{\dfrac{m_is_{j_2}}{m_{j_2}} - \dfrac{m_is_{j_1}}{m_{j_1}}}{\dfrac{m_i}{m_{j_2}} - \dfrac{m_i}{m_{j_1}}}$。

$s_i > \dfrac{\dfrac{s_{j_2}}{m_{j_2}}-\dfrac{s_{j_1}}{m_{j_1}}}{\dfrac{1}{m_{j_2}}-\dfrac{1}{m_{j_1}}}$。

用这个斜率式求上凸壳，就行了。

AC 代码：

#include<bits/stdc++.h>
#define double long double
using namespace std;
const int N = 1e6 + 10;
int n, hd = 1, tl, j;
double a[N], s[N], m[N], q[N], ans;
double x(int i) {
	return 1.0 / m[i];
}

double y(int i) {
	return s[i] / m[i];
}

double k(int i, int j) {
	return (y(j) - y(i)) * 1.0 / (x(j) - x(i));
}

int main() {
	cin >> n;
	m[0] = 1;

	for (int i = 1; i <= n; i++) {
		double x;
		cin >> x;
		a[i] = x / 1000000.0;
		s[i] = s[i - 1] + a[i] / (1.0 - a[i]);
		m[i] = m[i - 1] * (1.0 - a[i]);
	}

	q[++tl] = 0;

	for (int i = 1; i <= n; i++) {
		while (hd < tl && k(q[hd], q[hd + 1]) < s[i]) {
			hd++;
		}

		j = q[hd];
		ans = max(ans, (m[i] / m[j]) * (s[i] - s[j]) * 1.0);

		while (hd < tl && k(q[tl - 1], q[tl]) > k(q[tl - 1], i)) {
			tl--;
		}

		q[++tl] = i;
	}

	cout << (int)(ans * 1000000);
	return 0;
}

/*
*
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃   ━   ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃   ┻   ┃
* ┗━┓   ┏━┛  + +
*   ┃   ┃ + + + +Code is far away from
*   ┃   ┃ + bug with the llama protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug
*   ┃        ┣┓
*   ┃        ┏┛
*   ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/

//thanks cindy