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 的情况。
-
特判特殊情况以避免错误计算，确保左右字符可以拼接删除。
🏷️
