安 徽 省 机 器 人 大 赛 程 序 设 计 赛 道

Question

现在科研人员正在实验室中研制一种全新的清洁的可再生能源，该新能源的
主要成分为两种物质:物质α和物质β。现在科研人员有n个烧杯，t毫升物质β，
第 i 个烧杯中现在有 li 毫升物质α，若研制成功将得到 pi 毫升的新能源，而科研
人员可以在烧杯中加入整数毫升的物质β，研制成功的概率为(物质β的量)/(物
质α的量+物质β的量)。现在科研人员想要合理分配他们的物质β使得研制成功
的新能源的量期望值最大，但是一个烧杯中的物质β不能超过物质α的量，否则
会发生爆炸。现在烧杯中物质α的量将会发生 q 次变动，科研人员想要知道每次
变动之后他们能获得的新能源的量的最大期望值。
输入说明：
第一行三个正整数：n,t,q
第二行 n 个正整数：pi
第三行 n 个正整数：li
接下来的 q 行每行两个正整数：tj，rj。tj 为 1 或 2，1 表示增加 1 毫升物质
α，2 表示减少 1 毫升物质α，rj 为变动的烧杯编号。保证任意时刻所有烧杯不
为空
输出说明：
q 行实数表示每次变动之后的答案
如果绝对或相对误差不超过 1e-6，则答案将被视为正确。
输入样例：
15 / 20
2 1 3
4 5
1 2
1 1
1 2
2 1
输出样例：
1.666666667
1.333333333
2.000000000

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

【您想要解决的问题】： 您的问题是要解决一个优化问题，即如何合理分配给定的物质β到n个烧杯中，以最大化新能源的期望产量。这个问题涉及到概率论和动态规划，因为需要在每次烧杯中物质α的量变动后重新计算期望值。

【问题出现原因】： 这个问题出现的原因是科研人员需要在有限的物质β资源下，通过合理分配来获得最大的新能源产量。由于烧杯中物质β的量不能超过物质α的量，否则会发生爆炸，这增加了问题的复杂性。

【问题解决方案】： 最优解决方案需要考虑以下几个步骤：

1. 动态规划：使用动态规划来存储和更新每个烧杯在不同物质α和β配比下的期望产量。
2. 贪心算法：在每次变动后，使用贪心算法来分配物质β，以最大化当前的期望产量。
3. 概率计算：计算每个烧杯在当前物质α和β配比下的研制成功概率。
4. 期望值计算：基于研制成功概率和新能源产量，计算每个烧杯的期望产量。

【提供代码】： 由于这个问题的解决方案涉及到复杂的算法设计，下面提供一个简化的伪代码框架，以帮助理解问题解决的逻辑：

def maximize_expectation(n, t, q, p, l, changes):
    # 初始化动态规划表
    dp = [[0 for _ in range(t + 1)] for _ in range(sum(l) + 1)]
    
    # 填充动态规划表
    for i in range(n):
        for a in range(l[i] + 1):
            for b in range(t + 1):
                if a + b > 0:
                    dp[a][b] = calculate_expectation(a, b, p[i])
    
    # 处理变化
    for change in changes:
        a_change, cup_index = change
        l[cup_index - 1] += a_change
        # 重新计算期望值
        recalculate_expectation(cup_index - 1, l, dp)
    
    # 输出每次变化后的期望值
    for i in range(q):
        print(max(dp[l[i]]))

def calculate_expectation(a, b, p):
    # 计算单个烧杯的期望产量
    probability = b / (a + b)
    return probability * p

def recalculate_expectation(cup_index, l, dp):
    # 重新计算指定烧杯的期望值，并更新动态规划表
    pass

# 输入处理
n, t, q = map(int, input().split())
p = list(map(int, input().split()))
l = list(map(int, input().split()))
changes = [list(map(int, input().split())) for _ in range(q)]

# 解决问题
maximize_expectation(n, t, q, p, l, changes)

【代码运行方式】： 这段伪代码需要在Python环境中运行。您需要根据伪代码的逻辑，实现具体的动态规划填充、期望值计算和变化处理的函数。

【代码预期运行结果】： 代码运行后，将输出每次烧杯中物质α量变动后，新能源的期望产量的最大值。

【推荐相关链接】：

1. 动态规划算法基础
2. 贪心算法
3. 概率论基础
4. Python编程

请注意，以上提供的是一个解决问题的大致框架和思路，具体实现还需要根据问题的细节进行调整和优化。