动态规划初步
Update 2019.8.23 又回来刷题了。。。。 最近发现小绿本（《算法竞赛入门经典——习题与解答》）上的题值得一做，题解都写得很清真，不会像某谷上的题解，有一些奇技淫巧，不看 C o d e C o d e 的情况下一般都可以打出来，提高自己的代码实现能力。 然后我就先从动态规划开始吧 q w q q w q ~~ 小紫书 例题：9-1 题目链接：[ 洛谷 ] [ UVA ] 分析： 我觉得刘汝佳分析的思路写的很好，先抄下来： 时间是单向流逝的，是一个天然的 ”序“ 。影响到决策的只有当前时间和所处车站，所以可以用 d [ i ] [ j ] d [ i ] [ j ] 表示时刻 i i ，你在车站 j j ，最少还需要多少等待时间。边界条件是 d [ T ] [ n ] = 0 d [ T ] [ n ] = 0 ，其他 d [ T ] [ j ] = ∞ ( j ≠ n ) d [ T ] [ j ] = ∞ ( j ≠ n ) 。有 3 种决策： 等 1 分钟 做左边的车 做右边的车 然后反着推就可以啦~ 思路好清晰鸭 qwq，我写题解完全不能达到的水平…… C o d e C o d e ： 第一次打的时候用的是 E m a c s E m a c s ，然后我的配置文件有一点问题，然后编译以后代码就被吃了。。。。 劳资又 tm 打了一遍。。。。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 # include <i