December 13, 2022
经典两个堆。
背包。
经典 Tire 树 DP。
组合 dp。比赛写的是：
dp[i][j][k]：前 i 层，一共用了 j 个顶点，且第 i 层使用了 k 个。
转移 O(n) 一共 O(n4) 结果发现没办法简单的用前缀和降低复杂度。
正确的方法是简化状态！不考虑分了几层，直接用已经考察过的顶点数划分阶段：
dp[i][j]：一共用了 i 个顶点，且最外层使用了 j 个。
构造生成函数，贴多项式模板。
Posted by
xiaodao
Category: 日常
Your name - Required
Your email - Required (will not be published)
« ChatGPT 相关 | P3768 简单的数学题 »
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。