不难发现，对于一个区间 \([l, r]\)，恰好只有一个奶牛接受邀请的概率为
\[\prod_{i=l}^r(1-p_i) \cdot \sum_{i=l}^r \frac {p_i} {1-p_i}
\]
\]
设 \(m_a = \prod_{i=1}^a(1-p_i),\,s_a=\sum_{i=1}^a\frac{p_i}{1-p_i}\)，那么上面的式子可以表示为
\[\frac{m_r}{m_{l - 1}}\cdot (s_r-s_{l-1})
\]
\]
这个式子是凸的。它具有决策单调性，循环枚举 \(l\)，里面的 \(r\) 一定是递增的。
#include <cstdio>
inline double max(const double& a, const double& b){
return a > b ? a : b;
}
const int MAXN = 1e6 + 19;
int r = 1;
double p[MAXN], m = 1, s = 0, ans;
int n;
int main(){
std::scanf("%d", &n);
for(int i = 1; i <= n; ++i){
std::scanf("%lf", p + i);
p[i] /= 1e6;
ans = max(ans, p[i]);
}
for(int l = 1; l <= n; ++l){
while(r <= n && m * s <= m * (1 - p[r]) * (s + p[r] / (1 - p[r]))){//r 具有单调性
m *= 1 - p[r];
s += p[r] / (1 - p[r]);
++r;
}
ans = max(ans, m * s);//m * s 是选择[l,r]的概率
m /= 1 - p[l];
s -= p[l] / (1 - p[l]);//去除 l。
}
std::printf("%d\n", (int)(ans * 1e6));
return 0;
}
\(\quad\) 有点儿像斜率优化。