徐崇彦
2025 年6 月 6 日 12:36
1
题目ID：11054必做题100分
时间限制: 1000ms
空间限制: 524288kB
【问题描述】
由于可怜的bird还要一大堆的作业要做，他只能抽出H个小时去买彩票。由于抽奖地点都在一路公共汽车的线路上，所以怕麻烦的bird决定按车站的顺序抽奖，当然他可以从任意一站开始抽奖，对应经过的抽奖点可以买也可以不买。假设从第i个抽奖点到第i+1个抽奖点需要做Ci分钟的汽车。
潘柯翰
2025 年6 月 6 日 12:55
2
定义状态 ：
我们定义一个二维数组dp[i][j]，其中i表示当前抽到的第i个抽奖点，j表示剩余的时间（以分钟为单位）。dp[i][j]将存储在剩余时间为j分钟时，从第i个抽奖点开始所能获得的最大总中奖概率。
初始化 ：
初始化dp数组为0，其中dp[0][0]为初始值（即从第一个抽奖点开始且没有剩余时间时的中奖概率，即Pi的百万分之一）。
状态转移 ：
对于每个抽奖点i，遍历所有可能的剩余时间j（从H到0）。对于每个剩余时间，我们考虑两种情况：
如果当前剩余时间允许我们继续下一个抽奖点（即j > Ci + T），那么我们可以选择继续下一个抽奖点或者停留在当前点继续购买。最优解取决于两种情况的收益和哪一个更大。如果继续下一抽奖点获得的概率加得更多，那么选择转移。如果当前位置买更多的概率大（在有充足的时间且达到高收益概率时），那么停留在当前点并减少概率为下一轮做准备。
如果剩余时间不足以到达下一个抽奖点，则只能停留在当前点继续购买彩票直到时间耗尽。
计算概率 ：
每次转移时，都需要更新当前的中奖概率。如果选择继续下一个抽奖点，则用新的中奖概率计算下一个点的起始概率（百万分之Pi减去上次购买后减少的概率Di）。
结果输出 ：
遍历所有可能的时间情况，找出dp数组中的最大值即为所求的答案。
注意：这个问题的时间复杂度非常高，由于涉及了多个参数（时间、概率等）的组合。实际应用中可能需要优化算法以适应实际数据范围，或者通过记忆化搜索等方式减少重复计算以提高效率。由于这个问题涉及到概率和时间分配的复杂性，建议编写程序时充分考虑到算法的复杂性和边界情况。此外，也要注意精确的浮点数处理（虽然此题数据为整数，但仍然要注意程序中对浮点数的处理方式）。
在上述描述的基础上编写程序时还需要考虑到以下几点：
由于是在百万分之比值之间计算最大概率，可以考虑直接以百分数（0~1之间）存储来简化计算过程。
在选择下一行动（买或走）时需对每一步的可能收益进行估计并权衡选择。
可能需要采取适当的近似方法或者启发式搜索来减少计算量。
由于这是一个复杂的动态规划问题，完整的代码实现需要一定的编程技巧和算法设计能力。上述思路仅供参考，具体实现时还需要根据实际情况进行调整和优化。
1 个赞
潘柯翰
2025 年6 月 7 日 01:28
12
me？反正我是将老师以前讲的从录屏中打过去的虽然还没听特别懂qwq
1 个赞