题解 P5242 【[USACO19FEB]Cow Dating】

· · 题解

1.前言

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

2.做法

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

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