现在有 n 个烧杯,t 毫升物质β,第 i 个烧杯中现在有 li 毫升物质α,若研制 成功将得到 pi 毫升的新能源,而科研人员可以在烧杯中加入整数毫升的物质β。研制 成功的概率为(物质β的量) / (物质α的量 + 物质β的量)。合理分配物质β使得研制 成功的新能源的量期望值最大,一个烧杯中的物质β不能超过物质α的量。现在烧杯中 物质α的量将会发生 q 次变动,求每次变动之后能获得的新能源的量的最大期望值。 输入说明: 第一行 三个正整数: n, t, q (n 个烧杯,t 毫升物质β,q 次变动) 第二行 n 个正整数: pi (pi 毫升的新能源) 第三行 n 个正整数: li (第 i 个烧杯中现在有 li 毫升物质α) 接下来的 q 行每行两个正整数: tj,rj(tj 为 1 表示增加 1 毫升物质α, 2 表示减少 1 毫升物质α)。 rj 为变动的烧杯编号。
时间: 2024-03-30 13:33:39 浏览: 20
这是一个动态规划问题。我们可以定义状态 f[i][j] 表示前 i 个烧杯中加入 j 毫升物质β的最大期望新能源量。状态转移方程为:
f[i][j] = max{f[i-1][k] + p[i] * (j / (l[i]+j))} (0 <= k <= min(j, l[i]))
其中 p[i] 表示第 i 个烧杯可以得到的新能源量,l[i] 表示第 i 个烧杯中现在有的物质α的量。
对于每次变动,我们只需要更新受影响的烧杯的状态即可。具体来说,如果是增加物质α的操作,我们需要枚举加入的物质β的量 j,然后更新所有受影响的烧杯的状态 f[i][j];如果是减少物质α的操作,我们只需要更新受影响的烧杯的状态 f[rj][j]。
最终答案为 f[n][t]。
时间复杂度为 O(n^2t + qn^2)。如果使用滚动数组优化空间,可以将空间复杂度优化为 O(nt)。
相关问题
现在有 n 个烧杯,t 毫升物质β,第 i 个烧杯中现在有 li 毫升物质α,若研制 成功将得到 pi 毫升的新能源,而科研人员可以在烧杯中加入整数毫升的物质β。研制 成功的概率为(物质β的量) / (物质α的量 + 物质β的量)。合理分配物质β使得研制 成功的新能源的量期望值最大,一个烧杯中的物质β不能超过物质α的量。现在烧杯中 物质α的量将会发生 q 次变动,求每次变动之后能获得的新能源的量的最大期望值。
这是一个动态规划问题。我们定义一个状态 f[i][j] 表示前 i 个烧杯中分配了 j 毫升物质β时能获得的新能源的量的最大期望值。
对于每个状态 f[i][j],考虑当前第 i 个烧杯中的物质α的量为 a[i],则我们可以枚举这个烧杯中加入的物质β的量 k,其中 k 的范围为 0 到 a[i]。加入 k 毫升物质β后,第 i 个烧杯中物质α的量变为 a[i] - k,物质β的量变为 j + k。此时,研制成功的概率为 (j + k) / (a[i] + j)。因此,分配 k 毫升物质β后,能获得的新能源的量的期望值为 k * p[i] * (j + k) / (a[i] + j),其中 p[i] 表示研制成功后获得的新能源的量。
因此,状态转移方程为:
f[i][j] = max{f[i-1][j-k]+k*p[i]*(j+k)/(a[i]+j)},其中 0 <= k <= a[i]。
最后的答案为 f[n][0],表示前 n 个烧杯中分配了 0 毫升物质β时能获得的新能源的量的最大期望值。
每次烧杯中物质α的量发生变动时,我们只需要对所有状态 f[i][j] 进行一遍更新即可。
时间复杂度为 O(n^3)。
用砝码(50g),比重瓶,米尺,滴定管,铁架台,温度计,烧杯,细铁丝,匀质木棒等工具测量细小金属颗粒的密度
首先,将烧杯放在铁架台上并称量其重量,记为 $m_1$。然后,将一定量的细小金属颗粒放入烧杯中,再次称量其总重量,记为 $m_2$。用米尺测量烧杯中金属颗粒的体积,记为 $V$。然后,将比重瓶充满水,将比重瓶中的水倒入烧杯中覆盖金属颗粒,再用滴定管将气泡排出。用温度计测量水的温度,记为 $T$。用细铁丝将金属颗粒与水分离,其中金属颗粒会附着在细铁丝上。将细铁丝挂在比重瓶上,用滴定管滴定水的体积,记为 $V_1$。然后,将挂有金属颗粒的细铁丝放入比重瓶中,再次滴定水的体积,记为 $V_2$。
金属颗粒的密度可以通过以下公式计算:
$\rho=\frac{m_2-m_1}{V}-\frac{V_2-V_1}{T(V_2-V_1/V)}$
其中,$m_2-m_1$ 表示金属颗粒的质量,$V$ 表示金属颗粒的体积,$V_2-V_1$ 表示细铁丝与金属颗粒的总体积,$T$ 表示水的温度,$V_2-V_1/V$ 表示细铁丝的体积。将上述数据代入公式,即可求得金属颗粒的密度。