首页 > 其他 > 详细

# LuoGuP1282_多米诺骨牌

时间:2020-08-16 23:06:42      阅读:106      评论:0      收藏:0      [点我收藏+]

解:


题目要求在上下数字和的差值最小的情况下令反转次数最小

所以状态里要记上前i张骨牌的差值是多少

但是因为差值可能为负数,所以有以下两种处理方法:

1、平移值域

2、观察发现,不管如何翻转,前i张骨牌的上下数字之和为定值,
所以我们只要记录上面一行或下面一行数字的和,就知道了差值为多少

在这里用第2种方式,并记录上面一行,因为我看的题解是这么写的就懒得动了(雾

重新整理思路

设a[]表示上面一行的数字,b[]表示下面一行数字

设f[i][j]表示前i块骨牌,上面一行数字和为j时的最小翻转次数

初始化:f[][]全为inf,f[1][a[1]]=0,f[1][b[1]]=1

考虑转移:

若不翻这片骨牌,f[i][j]可以由f[i-1][j-a[i]]转移,前提是j-a[i]>=0

若翻这片骨牌,f[i][j]可以由f[i-1][j-b[i]]+1转移,前提是j-b[i]>=0

统计答案时:枚举k,依次考虑以f[n][k]是否能更新答案即可

枚举i是(n),枚举j是O(6n),因为总点数为6n,复杂度O(n^2)

# LuoGuP1282_多米诺骨牌

原文:https://www.cnblogs.com/Xiwon/p/13514937.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!