关于dp状态转移方程的设计2

187 字
1 分钟
关于dp状态转移方程的设计2

对于一些状态转移方程较好写的dp题,但是复杂度很难看,并且很难在数学方面上进行优化的dp题,我们可以考虑重构状态转移方程,比如要dp双线程操作的话,我们可以把一个线程写在方程里,另一个记录在数组的值里,这样就可以把看似暴力的方程优化成一个最普通的背包,相当于抽象了背包dp的重量和价值,这样的方程看起来有一种偏重关系,而且这样写兴许还可以处理两个线程的优先级,但是我还没见到过这样的题。

参考题目:P2224 [HNOI2001] 产品加工

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

关于dp状态转移方程的设计2
https://rechenz.github.io/post/关于dp状态转移方程的设计2/
作者
热尘
发布于
2023-10-18
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
热尘
游戏开发者 · AI 爱好者
公告
欢迎来到我的博客!这是一则示例公告。
分类
标签
站点统计
文章
38
分类
5
标签
12
总字数
46,029
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0

当前页面没有目录

文章目录

当前页面没有目录