题意：有一些高度为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即可。分四种情况讨论推导情况。
预处理一棵树往左/往右倒影响多少棵树。注意计算距离。