Makerlife 的小站
·
AT_ABC306D 题解
💡
原文中文，约2100字，阅读约需5分钟。
📝
内容提要
求高桥君在吃一份由n道菜组成的奇怪的全套菜单时，能够得到的最大的美味程度之和。使用动态规划解决。根据菜的毒素和解毒剂情况，分别讨论中毒和非中毒情况，计算出吃到第i道菜时，当前是否中毒的最大美味值。输出最大的美味程度之和。
🎯
关键要点
- 高桥君在餐厅里吃一份由n道菜组成的菜单，每道菜有美味程度和毒素情况。
- 如果吃了含毒素的菜，高桥君会拉肚子，若再吃毒素则会死亡。
- 目标是求得高桥君能够得到的最大的美味程度之和。
- 使用动态规划方法，设定状态f_i,1/0表示吃到第i道菜时的最大美味值。
- 根据菜的毒素情况，分为无毒和有毒两种情况进行讨论。
- 无毒情况下，考虑保持中毒状态和非中毒状态的最大美味值。
- 有毒情况下，考虑中毒状态和非中毒状态的最大美味值。
- 最终输出最大美味程度之和为max(f_n,0, f_n,1)。
➡️
