题意:给定一些火柴杆,问你可以组成多少种A-B=C这种形式的等式,注意,A,B,C都是正整数,并且没有前导0.

思路:这个题我们做的时候,要从低位到高位依次考虑。

对于当前位,剩下n个火柴的话,是否接受到前一位的进位,并且B是否已经达到最高位,C是否已经达到最高位。按照这个方式设计状态的话就可以转移了。

每次在转移的时候,枚举B的当前位的数字和C当前位的数字,就比较好写了。

这样的所有的状态最多就是 n*2*2*2,在考虑到枚举的过程最多是 10*10。也就是 总的计算次数大概在400000,速度很快。

 

HDU 3555 Bomb(数位dp初步)

这个题最主要的还是解决了我长期以来怎么求区间个数的问题。。 看着吧 http://blog.csdn.net/libin56842/article/details/9986693   ...

阅读全文

UVA 12063 – Zeros and Ones(动规计数,数位DP)

输入 n(位数) t(倍数) 用 d【i】【j】【k】 来表示  前 i 位 有 j 个 1 且余数 为 k 的个数。 那么 当 往前面加一位的时候。 一种情况是 往前面加的是 0 ...

阅读全文

欢迎留言

*