CFR 596 D. Wilbur and Trees ( Expectation DP )

Problem - D - Codeforces
We will try DP, but realize that merely with left and right bound parameter is insufficient for determining an answer, because if the leftmost tree is falling to the left, we need to know the direction of the fallen tree left to the leftmost tree. So we will need to also store the state of the left of leftmost and right of rightmost tree.
dp[ i ][ j ][ l ][ r ] : expectation of covered length, with tree[ i - 1 ] fallen left / right( l == 0 / 1 ), tree[ j + 1 ] fallen left / right( r == 0 / 1 )
For convenience, we will have the input in range[ 1, N ], position 0 and N + 1 infinitely far away.
For each stage there are only 4 transitions, either leftmost falls left or right, or rightmost falls left or right, if there is chain effect causing many falls, simply jump to the last tree that would fall, which could be preprocessed.
So there are O( n ^ 2 ) states, O( 1 ) transition, time complexity O( n ^ 2 ).

int N, H;
double P;
int X[ MAXN ];

int left_pos[ MAXN ], right_pos[ MAXN ]; // left_pos[ i ] : if i falls to left, the left most tree that will fall by chain effect

int vis[ MAXN ][ MAXN ][ 2 ][ 2 ];
double dp[ MAXN ][ MAXN ][ 2 ][ 2 ];

double dfs( int ql, int qr, int lt, int rt ){
    if( qr < ql ) return 0;
    if( vis[ ql ][ qr ][ lt ][ rt ] ) return dp[ ql ][ qr ][ lt ][ rt ];
    vis[ ql ][ qr ][ lt ][ rt ] = 1;
    double res = 0;
    if( true ){ // consider leftmost tree be cut
        int z = X[ ql - 1 ] + ( lt ? H : 0 ); // consider this tree falls to left, z is the position of the fallen left tree
        res += P * 0.5 * ( min( H, X[ ql ] - z ) + dfs( ql + 1, qr, 0, rt ) ); // falls to the left, either stretching fully or bumps to the adjacent fallen tree
        z = right_pos[ ql ];
        if( z < qr )
            res += ( 1.0 - P ) * 0.5 * ( X[ z ] + H - X[ ql ] + dfs( z + 1, qr, 1, rt ) );
        else{
            res += ( 1.0 - P ) * 0.5 * ( X[ qr ] - X[ ql ] );
            int p = X[ qr + 1 ] - ( not rt ? H : 0 );
            res += ( 1.0 - P ) * 0.5 * min( H, p - X[ qr ] );
        }
    }
    if( true ){ // consider rightmost tree be cut
        int z = X[ qr + 1 ] - ( not rt ? H : 0 );
        res += ( 1 - P ) * 0.5 * ( min( H, z - X[ qr ] ) + dfs( ql, qr - 1, lt, 1 ) );
        z = left_pos[ qr ];
        if( z > ql )
            res += P * 0.5 * ( X[ qr ] - X[ z ] + H + dfs( ql, z - 1, lt, 0 ) );
        else{
            res += P * 0.5 * ( X[ qr ] - X[ ql ] );
            int p = X[ ql - 1 ] + ( lt ? H : 0 );
            res += P * 0.5 * min( H, X[ ql ] - p );
        }
    }
    return dp[ ql ][ qr ][ lt ][ rt ] = res;
}

void solve(){
    cin >> N >> H >> P;
    for( int i = 1; i <= N; ++i )
        cin >> X[ i ];
    sort( X + 1, X + 1 + N );
    X[ 0 ] = -1e9, X[ N + 1 ] = 1e9;

    for( int i = 1; i <= N; ++i )
        left_pos[ i ] = ( X[ i ] - X[ i - 1 ] < H ? left_pos[ i - 1 ] : i );
    for( int i = N; i >= 1; --i )
        right_pos[ i ] = ( X[ i + 1 ] - X[ i ] < H ? right_pos[ i + 1 ] : i );

    cout << fixed << setprecision( 8 ) << dfs( 1, N, 0, 1 ) << "\n";
}