CF596D Wilbur and Trees

题意：有一些高度为h的树在数轴上。每次选择剩下的树中最左边或是最右边的树推倒（各50%概率），往左倒有p的概率，往右倒1-p。

一棵树倒了，如果挨到的另一棵树与该数的距离严格小于h，那么它也会往同方向倒。

问所有树都被推倒后的期望覆盖长度？

n<=2000.

标程：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int inf=1e8+;

 const int N=;

 int pos[N],h,n,L[N],R[N];

 double p,dp[N][N][][];

 int check(int op,int x,int dir)

 {

     if (op==)

     {

         if (!dir) return min(pos[x]-pos[x-],h);

         else return min(h,max(pos[x]-pos[x-]-h,));

     }else {

         if (!dir) return min(h,max(pos[x+]-pos[x]-h,));

         else return min(pos[x+]-pos[x],h);

     }

 }

 double dfs(int x,int y,int l,int r)

 {

     if (x>y) return ;

     if (dp[x][y][l][r]) return dp[x][y][l][r];

     double &ans=dp[x][y][l][r];

     //choose left

     ans+=0.5*p*(dfs(x+,y,,r)+check(,x,l));//fall left

     if (R[x]+<=y) ans+=0.5*(-p)*(dfs(R[x]+,y,,r)+pos[R[x]]-pos[x]+h);//fall right

       else ans+=0.5*(-p)*(pos[y]-pos[x]+check(,y,r));

     //choose right

     ans+=0.5*(-p)*(dfs(x,y-,l,)+check(,y,r));//fall right

     if (x<=L[y]-) ans+=0.5*p*(dfs(x,L[y]-,l,)+pos[y]-pos[L[y]]+h);//fall left

       else ans+=0.5*p*(pos[y]-pos[x]+check(,x,l));

     return ans;

 }

 int main()

 {

     scanf("%d%d%lf",&n,&h,&p);

     for (int i=;i<=n;i++) scanf("%d",&pos[i]);

     sort(pos+,pos+n+);pos[]=pos[]-h;pos[n+]=pos[n]+h;

     L[]=;R[n]=n;

     for (int i=;i<=n;i++)

       if (i==||pos[i]-pos[i-]<h) L[i]=L[i-];else L[i]=i;

     for (int i=n-;i>=;i--)

       if (i==n||pos[i+]-pos[i]<h) R[i]=R[i+];else R[i]=i;

     printf("%.10lf\n",dfs(,n,,));

    return ;

 }

易错点：1.注意长度的判断。分类讨论。

2.需要设置极值端点，和1树、n树的距离要>=h。

题解：区间dp

剩下的一段树一定是连续的，区间dp即可。分四种情况讨论推导情况。

预处理一棵树往左/往右倒影响多少棵树。注意计算距离。