CCPC 2021 Online - F 复盘:固定模式子序列 DP 与贡献划分
将芳香子序列按 nunhehheh 的最后一个 h 分类,用固定模式串子序列 DP 统计前缀方案,再乘上后缀 a 的非空选择数。重点复盘累计状态与当前位置新增状态的区别。
将芳香子序列按 nunhehheh 的最后一个 h 分类,用固定模式串子序列 DP 统计前缀方案,再乘上后缀 a 的非空选择数。重点复盘累计状态与当前位置新增状态的区别。
从洛谷 P1637 三元上升子序列出发,推广到 SPOJ INCSEQ 的长度 k 严格上升子序列计数问题,复盘分层动态规划与树状数组优化的通用做法。
复盘洛谷 P1121 环状最大两段子段和问题,通过分类讨论与对偶思想将环形选择转化为线性 DP,并分析非空约束下全负数组导致的边界错误与修正方法。
复盘洛谷 P1133 教主的花园问题,从线性 DP 的错误建模出发,分析环形约束下事后补丁方案的局限,并总结破环成链处理环形 DP 的正确做法。