题解 P5242 【[USACO19FEB]Cow Dating】

令$p_i$表示第i个位置是1的概率，$s_i=\prod_{k=1}^{i}(1-p_k)$,$t_i=\sum_{k=1}^{i}\frac{p_k}{1-p_k}$ 显然区间$[l,r]$的答案为 $$\frac{s_r}{s_{l-1}}(t_r-t_{l-1})$$ 固定右端点r，直观感觉到随着l的左移，乘积第二项变大，乘积第一项变小。所以猜到这个式子是凸的（我太菜了不会证），于是枚举右端点，整数三分左端点即可。 然而$s_i$太小了，会发生除零错。这个容易解决，把式子取个对数， $$\log(\frac{s_r}{s_{l-1}}(t_r-t_{l-1}))=\log{s_r}-\log{s_{l-1}}+\log(t_r-t_{l-1})$$ 最后把答案再exp一下，然后精度就不会有任何问题了。时间复杂度$O(n\log n)$。 常数太大了过不去怎么办？三分时判断语句里移一下项，运用$\log{a}-\log{b}=\log\frac{a}{b}$，就可以只做一次`log`运算，常数除以2。 有一个有趣的事情：对于随机的数据，答案很接近$\frac{1}{e}$。$e$这个神奇的常数居然又一次在貌似无关的地方出现了。 代码: ```cpp #include<bits/stdc++.h> using namespace std; using ld=long double; int n;ld a[1<<20],s[1<<20],t[1<<20],ans=-INFINITY; inline ld calc(int i,int j){return s[j]-s[i]+log(t[j]-t[i]);} ld tri(int l,int r,int p){ if(l==r)return calc(l,p); int mid=l+r>>1; if(-s[mid]+s[mid+1]<log((t[p]-t[mid+1])/(t[p]-t[mid])))return tri(mid+1,r,p); return tri(l,mid,p); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ int x;scanf("%d",&x); a[i]=x/1e6; t[i]=t[i-1]+a[i]/(1-a[i]); } for(int i=1;i<=n;i++)s[i]=s[i-1]+log(1-a[i]); for(int i=1;i<=n;i++)ans=max(ans,tri(0,i-1,i)); printf("%d\n",int(exp(ans)*1e6)); return 0; } ``` 下面是来自不会高中数学的本蒟蒻的证明 首先随便输入几个数据就会发现当$p_i\to 0$时最接近$\frac{1}{e}$，于是设x趋向于0，k为所需的序列长度 $$\lim_{x \to +0} (1-x)^kk\frac{x}{1-x}$$ $$(1-x)^kk\frac{x}{1-x}=(1-x)^{k-1}kx$$ $$((1-x)^{k-1}kx)'=x(k(1-x)^{k-1}\ln{(1-x)}+(1-x)^{k-1})$$ 令上式=0，得$k\ln{(1-x)}=-1$，$k=-\frac{1}{\ln{(1-x)}}$ 带入$\lim_{x \to +0} (1-x)^kk\frac{x}{1-x}$中 $$\textrm{原式}=\exp{(k\ln{(1-x)}+\ln(kx)-\ln{(1-x)})}$$ $$=\exp({-1+\ln{(\frac{x}{-\ln{(1-x)}})}-\ln{(1-x)}})$$ 显然$\ln({1-x})$趋向于0，另外考虑把$-\ln{(1-x)}$泰勒展开，得到 $$-\ln{(1-x)}=x+\frac{x^2}{2}+\frac{x^3}{3}+\frac{x^4}{4}+\ldots$$ 后面都是高阶无穷小，所以 $$\lim_{x \to +0}\frac{x}{-\ln{(1-x)}}=1$$ 于是该极限的值就是$e^{-1}$