题解 | 抽牌

import sys

n, pp, qq = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
dp = [[[0] * 1000 for _ in range(1000)] for _ in range(2)]

def e(p, q, l, r, sum_of_a):
    global pp, qq, dp, a
    if l == r:
        return a[l]
    if pp == q:
        if dp[0][l + 1][r] == 0:
            dp[0][l + 1][r] = e(q, p, l + 1, r, sum_of_a - a[l])
        if dp[0][l][r - 1] == 0:
            dp[0][l][r - 1] = e(q, p, l, r - 1, sum_of_a - a[r])
        return (p * (sum_of_a - dp[0][l + 1][r]) + (100 - p) * (sum_of_a - dp[0][l][r - 1])) / 100
    else:
        if dp[1][l + 1][r] == 0:
            dp[1][l + 1][r] = e(q, p, l + 1, r, sum_of_a - a[l])
        if dp[1][l][r - 1] == 0:
            dp[1][l][r - 1] = e(q, p, l, r - 1, sum_of_a - a[r])
        return (p * (sum_of_a - dp[1][l + 1][r]) + (100 - p) * (sum_of_a - dp[1][l][r - 1])) / 100

print("{:.3f}".format(e(pp, qq, 0, len(a) - 1, sum(a))))

记忆化搜索，记录子区间（l,r）内小明或者小方的取数期望，两个人的期望和等于区间数之和。