Article From:https://www.cnblogs.com/ljzalc1022/p/9064284.html

A person wants to cut down a row of N trees. He will wait for a probability to select the left or right tree at present. The probability of the tree has the probability of P to the left. The probability of 1-p is reversed to the right, the height of each tree on the number axis and the tree is given, and the expectation of the length of the tree is expected.

dp[l][r][lk][rk]Represents the direction of the [l, r] and L-1 trees falling in the interval, and the direction of the r+1 tree falling.
The updating method is more desirable and the details are more tedious

``````#include <bits/stdc++.h>
using namespace std;
const int maxn = 2005;
int h;
double p;
int a[maxn];
double dp[maxn][maxn][2][2];
double DW(int l,int r,int sl,int sr)
{
if (dp[l][r][sl][sr]) return dp[l][r][sl][sr];
if (l==r)
{
if (sl&&a[l-1]+h>a[l])
{
if (sr) return dp[l][r][sl][sr]=min(h,a[l+1]-a[l]);
else return dp[l][r][sl][sr]=min(h,max(0,a[r+1]-a[r]-h));
}
else if (!sr&&a[r+1]-h<a[r])
{
if (sl) return dp[l][r][sl][sr]=min(h,max(a[l]-a[l-1]-h,0));
else  return dp[l][r][sl][sr]=min(h,a[l]-a[l-1]);
}
double ans=0;
if (sl) ans+=p*min(h,max(a[l]-a[l-1]-h,0));
else ans+=p*min(h,a[l]-a[l-1]);
if (sr) ans+=(1-p)*min(h,a[r+1]-a[r]);
else ans+=(1-p)*min(h,max(0,a[r+1]-a[r]-h));
return dp[l][r][sl][sr]=ans;
}
if (sl&&a[l-1]+h>a[l])      return
dp[l][r][sl][sr]=DW(l+1,r,1,sr)+min(h,a[l+1]-a[l]);
else if(!sr&&a[r+1]-h<a[r]) return
dp[l][r][sl][sr]=DW(l,r-1,sl,0)+min(h,a[r]-a[r-1]);
double ans=0;
ans+=0.5*(1-p)*(DW(l+1,r,1,sr)+min(h,a[l+1]-a[l]));
ans+=0.5*p    *(DW(l,r-1,sl,0)+min(h,a[r]-a[r-1]));
if (sl) ans+=0.5*p*(DW(l+1,r,0,sr)+min(h,max(0,a[l]-a[l-1]-h)));
else    ans+=0.5*p*(DW(l+1,r,0,sr)+min(h,a[l]-a[l-1]));
if (sr) ans+=0.5*(1-p)*(DW(l,r-1,sl,1)+min(h,a[r+1]-a[r]));
else    ans+=0.5*(1-p)*(DW(l,r-1,sl,1)+min(h,max(0,a[r+1]-a[r]-h)));
return dp[l][r][sl][sr]=ans;
}
int main()
{
int n;
while (~scanf("%d%d%lf",&n,&h,&p))
{
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
memset(dp,0,sizeof(dp));
sort(a+1,a+n+1);
a[0]=a[1]-h;
a[n+1]=a[n]+h;
printf("%.12lf\n",DW(1,n,0,1));
}
return 0;
}
``````