题解 CF596D 【Wilbur and Trees】

发表于 | 更新于

$Description$

有$n$课树并排排列，每棵树高$h$。每次从剩余的树中选最左边的或最右边的（概率相等为$0.5$），砍掉一棵树，树倒向左边的概率为$p$，倒向右边的概率为$1-p$。如果树和相邻树的距离小于$h$，树倒时会把相邻的树撞倒，倒的方向和撞到它的树一致。问，砍完所有树，树干覆盖的草地长度的期望值。

$Solution:$

容易发现,砍树是从两端开始砍的，因此两端会影响中间，而中间则不会影响到两端的树，因为砍到中间的时候，两端的树都已经砍过了.所以做$dp$的时候，例如正在处理区间$i$到$j$，我们不需要关注区间内的树是向哪边倒的，因为中间的树不会影响两端的，我们需要关注的是$i-1$和$j+1$位的地方的树，因为只有这些地方会对中间的树有影响，所以我们用$dp[i][j][0/1][0/1]$来表式$i-1$和$j+1$这两棵树的状态时，$i$到$j$之间的答案。若状态若为$0$，则表示向左侧倒，若为$1$，则表示向右侧倒。

接下来分类讨论:

$1.$第$i$颗树向左倒，不会影响别的树

$2.$第$j$棵树向右倒，不会影响别的树

$3.$第$i$棵树向右倒，会影响到第$i$棵树右边的树

$(1)$第$i$棵树能把$(i+1)$~$j$之间的所有树都压倒

$(2)$第$i$棵树不能把$(i+1)$~$j$之间的所有树都压倒

$4.$第$j$棵树向左倒，会影响到前面的树

$(1)$第$j$棵树能把$i$~$(j-1)$之间的所有树都压倒

$(2)$第$j$棵树不能把$i$~$(j-1)$之间的所有树都压倒

采用记搜实现

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define N 2007
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
} 
int loc[N],dl[N],dr[N],h,n;
double f[N][N][2][2],p,q;
double dfs(int l,int r,int x,int y){
    if (l>r)return 0;
    if (f[l][r][x][y]!=-1)return f[l][r][x][y];
    double res=0,L=min(h,loc[l]-loc[l-1]-x*h),R=min(h,loc[r+1]-loc[r]-(!y)*h);
    res+=0.5*p*(dfs(l+1,r,0,y)+L);//最左边向左倒
    res+=0.5*q*(dfs(l,r-1,x,1)+R);//最右边向右倒
    if (dl[r]<=l)res+=0.5*p*(loc[r]-loc[l]+L);
    else res+=0.5*p*(dfs(l,dl[r]-1,x,0)+loc[r]-loc[dl[r]]+h);// 最右边的向左倒，且能覆盖整个区间的树
    if (dr[l]>=r)res+=0.5*q*(loc[r]-loc[l]+R);
    else res+=0.5*q*(dfs(dr[l]+1,r,1,y)+loc[dr[l]]-loc[l]+h);// 最左边的向右倒，且能覆盖整个区间的树
    return f[l][r][x][y]=res;
}
signed main(){
    n=read();cin>>h>>p;q=1-p;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            for (int x=0;x<2;++x)
                for (int y=0;y<2;++y)
                    f[i][j][x][y]=-1.0;
    for (int i=1;i<=n;++i)loc[i]=read();
    sort(loc+1,loc+1+n);loc[0]=-inf;loc[n+1]=inf;
    dl[1]=1;
    for (int i=2;i<=n;++i)
        if (loc[i]-loc[i-1]<h)dl[i]=dl[i-1];
        else dl[i]=i;
    dr[n]=n;
    for (int i=n-1;i;--i)
        if (loc[i+1]-loc[i]<h)dr[i]=dr[i+1];
        else dr[i]=i;
    //dl[i],dr[i]分别表示从i这棵树开始向左/右最多能覆盖到第dl[i]/dr[i]棵树
    printf("%.9lf\n",dfs(1,n,0,1));    
}