首页 > 试题广场 >

抽牌

[编程题]抽牌

热度指数：884 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

桌上放了一堆牌，牌从上到下由 1 到 n 编号，每张牌上写有一个数字，第 i 张牌上的数字为 a_i，小明和小方在玩轮流取牌的游戏，每次每个人只能取一张牌，小明先取牌。

取牌规则如下，当一个人取牌时，他只能取当前牌堆中的最上面的一张或者最下面一张。小明和小方都采用随机取牌的策略，小明每次以概率 p 取最上面一张牌，以概率 1-p 取最下面一张牌；小方每次以概率 q 取最上面一张牌，以概率 1-q 取最下面一张牌。

最后两人的得分为他们各自取到排上的数字之和。问小明得分的数学期望。

数据范围： $1 \le n \le 1000 \$ ， $0 \le P，Q \le 100 \$ ， $1 \le a_i \le 13 \$ 。

输入描述:

第一行输入三个整数 n , P , Q。小明取最上面一张牌的概率 p=P/100 ，小方取最上面一张牌的概率 q=Q/100。
接下来一行 n 个数，每张牌上的数字。

输出描述:

输出答案，四舍五入保留三位小数。

示例1

输入

2 10 90
1 2

输出

1.900

示例2

输入

5 10 20
1 3 4 5 13

输出

18.038

算法知识视频讲解

Python3

饥饿的杰尼龟要发财

arr = [int(_) for _ in input().split()]
n, P, Q = arr[0], arr[1], arr[2]
p, q = P / 100, Q / 100
arr = [int(_) for _ in input().split()]
dp = [[0] * n for _ in range(n)]


def func(begin: int, end: int):
    if begin == end:
        dp[begin][end] = arr[begin]
        return
    elif end - begin == 1:
        dp[begin][end] = p * arr[begin] + (1 - p) * arr[end]
        return
    # 甲顶乙顶 选择概率 *(本次选择得分+之前得分)
    # 甲顶乙底
    # 甲底乙顶
    # 甲底乙底
    dp[begin][end] = (
        p * q * (arr[begin] + dp[begin + 2][end])
        + p * (1 - q) * (arr[begin] + dp[begin + 1][end - 1])
        + (1 - p) * q * (arr[end] + dp[begin + 1][end - 1])
        + (1 - p) * (1 - q) * (arr[end] + dp[begin][end - 2])
    )


for gap in range(n):
    for start in range(n):
        end = start + gap
        if end < n:
            func(start, end)
            # print(start, end, end='\t')
        else:
            break
    # print()
print("{:.3f}".format(dp[0][n - 1]))

发表于 2023-03-17 18:13:05 回复(0)