专栏文章
DPtrick : 延迟钦定 / 贡献延后计算
算法·理论参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mincke0w
- 此快照首次捕获于
- 2025/12/02 00:12 3 个月前
- 此快照最后确认于
- 2025/12/02 00:12 3 个月前
首先我很菜,这东西只是给自己用的,见得少,难免以偏概全,错别字也请包容
这个东西的实质就是说当做一个dp的问题的时候,如果有的贡献不能在当下立刻计算,而是需要在未来某一个时间计算时就可以使用这个trick
或者形如的形式也是可以使用这个技巧的,但是需要先将值(这里指值和下标扔到一起)排序。
排序的意义在于让贡献可以被延后计算而不是完全没有办法计算,这个是在Min处取到贡献,那么就应该让值从小到大去扫描。
上文这个还要结合另一个trick:将排列的匹配转化为二分图的匹配
dp状态设计的时候自然需要多一维度维护有几个点是钦定在未来计算(和某一个特定值有一定大小关系)
例题:P14364,AT_arc207_a,QOJ2573
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...