砍树自动机（鲁迅很生气）

题意：

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;
}