1000ms

Difficulty: 5

所属公司 : 蚂蚁

时间 :2025年9月7日-算法岗

算法与标签>动态规划

会员或题库专享

请先，开通会员或购买题库蚂蚁机考题库，可解锁完整内容。

购买蚂蚁机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（蚂蚁机考题库），可解锁完整内容。

购买题库开通会员

思路

定义动态规划：令 $f_i$ 表示在第 $i$ 周开始且当前不被禁赛时，从第 $i$ 周到赛季结束的最大期望。
决策：
- 参加第 $i$ 场：得到期望 $p_i$ ，并且以 $1-q_i$ 进入状态 $f_{i+1}$ ，以 $q_i$ 被禁赛而跳到 $f_{i+2}$ 。
- 跳过第 $i$ 场：保持不被禁赛，进入 $f_{i+1}$ 。
转移

题目内容

铁制品工艺练习赛(Iron Craft Practising Contest，ICPC)赛季即将开始。在接下来的连续 $n$ 周内，每周将在某个城市举行一次比赛。

根据经验，小C在第 $i$ 场比赛中成功打铁的概率为 $p_i$ 。

如果小C参加比赛，则在赛后有 $q_i$ 的概率被教练禁止参加下一周（即第 $i+1$ 周）的比赛。无论他是否参加第 $i+1$ 周的比赛，此禁令都会在第 $i+1$ 周结束后自动解除。

小C可以选择任意场比赛参加。小C希望最大化本赛季打铁次数的期望值。