CF2B The least round way 题解

题目传送门

题意(直接复制了QWQ)

题目描述

给定由非负整数组成的$n \times n$的正方形矩阵,你需要寻找一条路径:
以左上角为起点,
每次只能向右或向下走,
以右下角为终点 并且,如果我们把沿路遇到的数进行相乘,积应当是最小“round”,换句话说,应当以最小数目的0的结尾.

输入格式

第一行包含一个整数 $(2 \leq n \leq 1000)$,$n$为矩阵的规模,接下来的$n$行包含矩阵的元素(不超过$10^9$的非负整数).

输出格式

第一行应包含最小尾0的个数,第二行打印出相应的路径(译注:D为下,R为右)

思路

楼下其实说得蛮清楚了,我主要就是说一下坑。。。
构成末尾是0的只能是$2^a$与$5^b$相乘,所得的0的个数为$min(a,b)$,所以,只要2、5分别dp一遍,取一下上与左的最小值就好啦。。。最后求路径时递归求一遍就好啦。。。

TLE的小朋友们看这里啦。。。

TLE的小朋友们看这里啦。。。

TLE的小朋友们看这里啦。。。

(重要的事情说三遍)

此题特别会卡时。
比如说一开始预处理每个数是$2^a$与$2^b$时,需要将此数不间断地除下去,为什么呢?因为卡常数。。。也许时我RP的原因吧。。。卡了半天,终于卡过去了。。。
具体详见代码:

代码

(我知道你要看这个)
暂无评论

发送评论


				
上一篇
下一篇