Makerlife 的小站
·
AtCoder DP 系列刷题记录
💡
原文中文，约2100字，阅读约需5分钟。
📝
内容提要
本文讨论了动态规划问题，其中目标是通过在不同的天完成任务来最大化幸福感。文章提供了解决问题的转移方程和核心代码。
🎯
关键要点
- 讨论动态规划问题，目标是通过在不同的天完成任务来最大化幸福感。
- 定义 f_i,j 表示截止到第 i 天时做第 j 件事的幸福值总和。
- 提供转移方程：f_{i,1} = max(f_{i-1,2}, f_{i-1,3})，f_{i,2} = max(f_{i-1,1}, f_{i-1,3})，f_{i,3} = max(f_{i-1,1}, f_{i-1,2})。
- 核心代码展示了如何计算每一天的幸福值。
- 讨论石子游戏，设 f_i 表示剩余 i 枚石子的输赢情况。
- 当且仅当当前操作的上一步操作必输时，当前操作才可以必胜。
- 初始化 f_0 = 0，提供状态转移方程。
- 区间 DP 问题，定义 f_{i,j} 记录 i 到 j 能删掉多少字符。
- 答案计算为最大的步数，考虑分界点 k 的情况。
- 特判特殊情况以避免错误计算，确保左右字符可以拼接删除。
➡️
