poj 1509 Glass Beads 最大最小表示板题

继续学习最大最小表示这种精巧的算法~ poj 1509 Glass Beads

bzoj 1016 最小生成树计数

08年 IOI 国家队论文《矩阵乘法在信息学中的应用 · 浙江省杭州二中俞华程》中的第一个例子~ bzoj 1494 NOI2007 生成树计数

【1】和【2】中我们通过dijkstra、spfa两种方法给出了次短路模板. 现在我们研究次短路的条数问题. poj 3463 Sightseeing

【1】中使用了dijkstra的姿势切了次短路的模板题~ 现在再使用spfa的姿势切一次~ 其实纵观【1】的解题过程, dijkstra和spfa本质上都是松弛边而已.

【1】已经研究了01背包K优解的问题. 现在继续 rqnoj 123 多人背包

本题和【1】的区别在于本题 不同策略相同权值视为不同, 而【1】是 不同策略相同权值视为相同。这就是《背包九讲2.0》 9.5 最后一个自然段讨论的两种情况

1
2
3

另外还要注意题目对于“第K优解”的定义，是要求将策略不同但权值相同
的两个方案是看作同一个解还是不同的解。如果是前者，则维护有序队列时要
保证队列里的数没有重复的。

崔天翼神犇的《背包九讲2.0》 9.5节讲解了背包问题K优解问题的解法. 崔神犇总结到

1
2

对于求次优解、第K优解类的问题，如果相应的最优解问题能写出状态转移方程、用动态规划解决，
那么求次优解往往可以相同的复杂度解决，第K优解则比求最优解的复杂度上多一个系数K。