hdu 3709 Balanced Number (数位dp)

题目链接
题意:找到某区间中平衡数的个数。所谓平衡数是指,存在某个位置,值得两边的力矩相等。举个例子。。比如14326,如果把4作为中间。。那么左边=1*1=1 右边=3*1+2*2+6*2=19。。。
思路:枚举中间的pivot。。。注意如果是个位数也是平衡数(就是认为两边的力矩都是0了。。。),所以每一个位置都可能是平衡位置。。枚举的时候从1到len…
一开始我是分别记录两边的值。。非常浪费空间。。。然而发现其实没必要。。我们只关心左边是否相等。。而不关心左右的值到底是多少。。所以可以把两边的值带符号合并成一个值(pivot左边为+,pivot右边为负)。。。如果最后为0。。说明左右相等。。。

以及。。这个值(设为sum)是递减的。。。所以任何时刻如果sum<0。。那么狗带。。算一个剪枝。。而且避免了下标为负。。。

以及,关于前导0的问题。。。有些题目不允许前导0.。。。但是并不是所有不允许前导0的都需要特别处理。。。像这道。。前导0不会导致更新答案。。。所以不用管。。。 但是要注意。。。由于0,00,000,0000都是合法的balanced数。。。然而其实他们是一个数。。多加了len-1次。。记得减去。

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz