题目要求在上下数字和的差值最小的情况下令反转次数最小
所以状态里要记上前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)
原文:https://www.cnblogs.com/Xiwon/p/13514937.html