动态规划模型 动态规划经典模型之线性模型

关注我们的微信平台，定期推送账号信息新闻、竞赛自主报名、信息学专业知识、信息学疑难解答、信息学训练营信息等诸多优质内容。欢迎与朋友或朋友圈分享文章！NOIP2018冬令营热映中！

信息学竞赛的各类考试基本都会出现动态规划。对于信息学学生来说，理解和学习动态规划的思想是非常重要的。

我们之前已经介绍过了(点击查看):

dp中最常用的模型

这里的线性是指状态的排列是线性的。

[例子]在一个黑暗多风的夜晚，有n (n

想法一:贪心算法。如果跑得最快的人总是往回跑，那么每当有人过桥时，他就必须跟上。不过看一组数据，四个人过桥的时间分别是1 2 5 10。按照贪心算法，答案是19，但实际答案应该是17。

具体步骤如下:

第一步:1和2通过，花时间2，然后1回来(花时间1)；

第二次:3和4通过，需要10，然后2回来(需要2)；

第3部分:1和2通过，用了2，共17次。

所以贪心是不对的。

想法二:动态规划。

让我们按照花费时间的升序对所有人进行排序，并假设第一批过河的人花费的最小时间是opt[i]。

看初始状态:opt[0]=0，opt[1]=T[1]，opt[2]=T[2]...

看最后状态:最后只有两种情况

情况一:岸上只剩下一个人。最后，我和我会一起过河。

状态转移方程:opt[i] = opt[i-1]+T[1]+T[i]

其中，opt[i-1]是i-1在另一边的最小时间，所以此时手电筒必须在另一边；T[1]是把手电筒送回去的时间；T[i]是最后一次穿越。

情况二:岸上只剩下两个人。最后一次穿越将是1和2一起过河。

状态转移方程:opt[I]= opt[I-2]+t[1]+t[I]+t[2]+t[2]

其中，opt[i-2]是i-2人在另一边的最小时间，所以此时手电筒必须在另一边；T[1]是把手电筒送回去的时间；T[1]是最后一次过河(我是目前为止最后一个，所以肯定比另一个人慢)，第一个T[2]是把手电筒送回去的时间；第二个T[2]是2和1一起过河的时间。

这最后两种情况其实是相互对应的:每个人都可以选择1过河，也可以选择1和2之外的人。

那么总状态转移方程取两者中的最小值

opt[i] = min{opt[i-1] + a[1] + a[i]，opt[i-2] + a[1] + a[i] + 2*a[2] }

[例子]在一个黑暗多风的夜晚，有n (n

想法一:贪心算法。如果跑得最快的人总是往回跑，那么每当有人过桥时，他就必须跟上。不过看一组数据，四个人过桥的时间分别是1 2 5 10。按照贪心算法，答案是19，但实际答案应该是17。

具体步骤如下:

第一步:1和2通过，花时间2，然后1回来(花时间1)；

第二次:3和4通过，需要10，然后2回来(需要2)；

第3部分:1和2通过，用了2，共17次。

所以贪心是不对的。

想法二:动态规划。

让我们按照花费时间的升序对所有人进行排序，并假设第一批过河的人花费的最小时间是opt[i]。

看初始状态:opt[0]=0，opt[1]=T[1]，opt[2]=T[2]...

看最后状态:最后只有两种情况

情况一:岸上只剩下一个人。最后，我和我会一起过河。

状态转移方程:opt[i] = opt[i-1]+T[1]+T[i]

其中，opt[i-1]是i-1在另一边的最小时间，所以此时手电筒必须在另一边；T[1]是把手电筒送回去的时间；T[i]是最后一次穿越。

情况二:岸上只剩下两个人。最后一次穿越将是1和2一起过河。

状态转移方程:opt[I]= opt[I-2]+t[1]+t[I]+t[2]+t[2]

其中，opt[i-2]是i-2人在另一边的最小时间，所以此时手电筒必须在另一边；T[1]是把手电筒送回去的时间；T[1]是最后一次过河(我是目前为止最后一个，所以肯定比另一个人慢)，第一个T[2]是把手电筒送回去的时间；第二个T[2]是2和1一起过河的时间。

这最后两种情况其实是相互对应的:每个人都可以选择1过河，也可以选择1和2之外的人。

那么总状态转移方程取两者中的最小值

opt[i] = min{opt[i-1] + a[1] + a[i]，opt[i-2] + a[1] + a[i] + 2*a[2] }

寒假来冬令营提升自己~