现在的位置: 首页 > 综合 > 正文

codeforces好题记录——2B

2018年02月23日 ⁄ 综合 ⁄ 共 434字 ⁄ 字号 评论关闭
题目见http://codeforces.com/problemset/problem/2/B

给定一个正方形数组,只能向下或向右移动,求从左上移动到右下,在这个路径上的所有数字的乘积末尾的0最少。
考虑到要使乘积末尾有0,则路径上必须有10,或者有2和5,有几个10末尾就有几个0
这里是一个求最优的问题,考虑用dp来做,要求就是路径上2和5的个数中的最小值最小!!!但是这样直接dp是不好做的,这时大神的智慧就发挥了,我却怎么也没想到,我们可以对“2最少”这个条件和“5最少”这个条件分别dp一次。这样“2最少”找出的路径中5的个数一定大于“5最少”的路径中5的个数的,所以
                              min(2, 5) = min(min(2), min(5))

d(i, j)表示终点为(i, j)时最小的2或5的个数
F(k)表示k分解因数中2或5的个数
v(i, j)表示原本的值
d(i, j) = F(v(i, j)) + min(d(i -  1, j), d(i, j - 1))
要注意考虑边界情况

抱歉!评论已关闭.