HDU 3709 数位dp:定义一种平衡数,就是按照十进制数位上选取一位当作支点,左右两边的数位计算力矩后相等,即为平衡数。
所谓力矩,就是拿数位上的数字乘上到支点的距离。举例来说,4139,如果选3作为支点,左边的力矩为4*2+1*1=9,右边的力矩为9*1=9,左边等于右边,所以4139是一个平衡数。题目要求计算出区间[x,y]之间的平衡数的个数。
思路:显然数位dp。关键是在于状态的设计,这里还是欠缺不少。对于平衡的题目设计状态,经常要用到平衡度的思想,所谓平衡度就是定义为右边的重量-左边的重量,当平衡度为0时显然为平衡。这里要注意到,任意一个数,如果是平衡数,只存在一个数位当支点满足条件,不存在第二组解。所以如果我们设计状态dp[pos][pivot][balance],其中pos为数位长度,pivot为支点位置,balance为平衡度。这样起码可以保证不同pos不同pivot之间的数一定没有重复。 利用平衡度来设计状态,就很好设计状态转移了,因为平衡状态是由不平衡状态转移过来的。这样只要枚举pivot的位置,将所有的结果相加就可以。 还有一点要注意,枚举一共有pos次,这其中0被多算了pos-1次,因为无论枚举哪个数位做pivot,0都是满足条件的,所以最后结果要减掉。具体细节见代码。代码:就爱阅读www.92to.com网友整理上传,为您提供最全的知识大全,期待您的分享,转载请注明出处。
来源: