砍树自动机(鲁迅很生气)

题意:

Wilbur的门前有2棵枣树很多棵枣树排成一排(n<=2000),枣树的高度均为h。wilbur为了成为一只beaver(河狸),发明了砍树自动机。它会每次选择这一列树两端的某一棵树(各有0.5的概率被选择),将其砍倒,受风速的影响,砍倒的树会有p的概率向左倒,(1-p)的概率向右倒,如果倒下的树的高度严格大于倒向的树,会将倒向的树碰倒,以此类推,直到连锁反应完成。现在Wilbur想知道当他砍倒所有树了之后,倒下的树干覆盖地面的期望长度是多少。

思路:

是不是十分懵逼?这尼玛是啥子东西,又是概率又是期望又是连锁反反应的。
但是仔细想一想,会发现这道题其实是有规律可循的。
1.因为如题的描述,枣树一定会成段从两边倒下,而且中间没有倒的枣树一定是连续的。所以这很适合动态规划。很自然想到用f(l,r,lf,rf)表示从l到r的枣树,其中第l-1棵向lf方向倒,r+1棵向rf方向倒,砍倒这(r-l+1)棵枣树后覆盖地面的贡献(就是这r-l+1棵枣树自己覆盖了多长)。
2.因为如题的描述,和复杂的状态定义,以及状态之间复杂的制约关系,我们最好采用记忆话搜索。
于是我们细心地写出状态转移方程。以及一些辅助函数。

我们先定义方向的表示:无论在变量命名中还是在状态转移中都可以使我们的思路更加清晰:
#define L 0:L表示左边
#define R 0:R表示右边
然后我们定义f()和一些辅助数组
f(l,r,lf,rf) :如上所述
pos[x] :第x棵树的位置
lft[x] :第x棵树倒向左方最远波及的树是第几棵
rgt[x] :第x棵树倒向右方最远波及的树是第几棵
bdl[x][f] :第x棵树倒向右时树顶的位置或倒向左时树根的位置
bdr[x][f] :第x棵树倒向左是树顶的位置或倒向右时树根的位置
在状态转移时,还需要注意几个事实:
如果第8棵树向左倒可以波及倒第1棵树,但是此时的区间为[5,8],我们就默认它只能波及倒第5棵树,所以在转移时还涉及到两个变量:
rlc=max(l,lft[r]) :表示右边的树向左倒波及到的最左边的树
lrc=min(r,rgt[l]) :表示左边的树向右倒波及到的最右边的树
如果左边的树向左倒或右边的树向右倒,有可能因为l-1和r+1的原因,没法贡献h的长度,所以这个也要在状态转移中注意
最后,我们再添加几个帮助转移的变量:
pll:Wilbur选择了砍左边的树,左边的树被砍倒后向左倒
plr:左树右倒
prl:右树左倒
prr:右树右倒

然后我们就可以写出状态转移方程:

当然,我们先求解pll,plr,prl,prr:
$$
\begin{cases}
pll=0.5\times p \\
plr=0.5\times (1-p) \\
prl=0.5\times p \\
prr=0.5\times (1-p)
\end{cases}
$$

做完了这所有的准备工作,我们就可以转移状态了。由于latex装不下这么长的公式,我直接用文本

f(l,r,lf,rf) = pll*(f(l+1,r,L,rf)+min(pos[l]-bdl[l-1][fl],h));

                  + plr*(f(rgt(l)+1,r,R,rf)+min(pos[lrc]-pos[l]+h,bdr[r+1][fr]-pos[l]));

                  + prl*(f(l,lft(t)-1,lf,L)+min(pos[r]-pos[rlc]+h,pos[r]-bdl[l-1][fl]));

                  + prr*(f(l,r-1,fl,R)+min(bdr[r+1][fr]-pos[r],h));

然后我们我们就可以记忆化搜索。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define L 0
#define R 1
#define MX 2102

using namespace std;

double f[MX][MX][2][2];
int bdl[MX][2],bdr[MX][2];
int lft[MX],rgt[MX];
int pos[MX];
int n,h;
double p;

double sch(int l,int r,int fl,int fr)
{
    double ret=0;
    if(f[l][r][fl][fr]>-1)return f[l][r][fl][fr];
    if(l>r)return 0;
    double pll,plr,prl,prr;
    int rlc,lrc;
    rlc=max(l,lft[r]);
    lrc=min(r,rgt[l]);
    pll=0.5*p;
    plr=0.5*(1-p);
    prl=0.5*p;
    prr=0.5*(1-p);
    ret+=pll*(sch(l+1,r,L,fr)+(double)min(pos[l]-bdl[l-1][fl],h));
    ret+=plr*(sch(rgt[l]+1,r,R,fr)+(double)(min(pos[lrc]-pos[l]+h,bdr[r+1][fr]-pos[l])));
    ret+=prl*(sch(l,lft[r]-1,fl,L)+(double)(min(pos[r]-pos[rlc]+h,pos[r]-bdl[l-1][fl])));
    ret+=prr*(sch(l,r-1,fl,R)+(double)min(bdr[r+1][fr]-pos[r],h));
    f[l][r][fl][fr]=ret;
    return ret;
}

void input()
{
    scanf("%d%d%lf",&n,&h,&p);
    for(int i=1;i<=n;i++)scanf("%d",&pos[i]);
    sort(pos+1,pos+n+1);
    pos[0]=-500000000,pos[n+1]=500000000;
    lft[0]=0;
    for(int i=1;i<=n;i++)
        if(pos[i]-pos[i-1]<h)lft[i]=lft[i-1];
        else lft[i]=i;
    rgt[n+1]=n+1;
    for(int i=n;i>=1;i--)
        if(pos[i+1]-pos[i]<h)rgt[i]=rgt[i+1];
        else rgt[i]=i;
    for(int i=0;i<=n+1;i++)
        bdl[i][L]=pos[i],bdl[i][R]=pos[i]+h,bdr[i][L]=pos[i]-h,bdr[i][R]=pos[i];
}

int main()
{
    input();
    for(int i=0;i<=n+1;i++)
        for(int j=0;j<=n+1;j++)
            f[i][j][L][L]=f[i][j][L][R]=f[i][j][R][L]=f[i][j][R][R]=-1;
    printf("%.15f\n",sch(1,n,L,R));
    return 0;
}


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *