NOIP2009提高组.Hankson的趣味题

数论算法

信息学奥赛一本通 1505：【例 2】双调路径 | 洛谷 P5530 [BalticOI 2002] 双调路径

阶段：到达顶点编号i，路径费用j（或者此处也可以选择使用取路径时间，本题中费用和时间是等价的）决策：从某顶点出发下一步到哪个顶点策略：路径策略集合：从源点s出发到顶点i的路径费用为j的所有路径条件：时间最小在路径费用固定的情况下，只有时间最小的路径才可能是最“小”路径，时间更大的路径没有必要统计。因此只需要统计费用固定的所有路径中时间最小的路径的最小时间。统计量：时间状态定义dpijdp_{i,j

2012NOIP提高组之国王游戏求解与贪心算法