$CF2B\ The \ least\ round\ way$

problem

题目大意：求一条路径\(from(1,1)\ to (n,n)\)

求0的个数 无非就是拆解 有几个10乘起来
$10?= ?2 ?* ?5 $
那么单独存在$ 2?or ?5$的时候肯定不能构成。
设一条路径有x个2 y个5。
所以就是求一条路径下的 \(Min(x,y)\)
也就需要预处理出来 方格的每个数字 存在几个2 几个5 。
跑两遍DP。两次最少的肯定最少。

还有一个细节问题。 如果存在0的话。需要特判输出1。

原题要输出路径 需要去用数组存一下路径。

#ifdef Dubug

#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long LL ;
inline LL In() {
    LL res(0),f(1);
    register char c ;
    while(isspace(c=getchar())) ;
    c == '-'? f = -1 , c = getchar() : 0 ;
    while(res = (res << 1) + (res << 3) + (c & 15) , isdigit(c=getchar())) ;
    return res * f ;
}
int n , m ;
const int N = 1000 + 5 ;
int cnt2[N][N] ;
int cnt5[N][N] ;
pair<int,int>dp[N][N] ;
inline int ret(int x,int y) {
    int cnt = 0 ;
    while(x % y == 0) cnt ++ , x /= y ;
    return cnt ;
}
inline void Ot() {
#define fir first
#define se second
    for(register int i=1; i<=n; i++) dp[1][i].fir = cnt2[1][i] + dp[1][i-1].fir ;
    for(register int i=1; i<=n; i++) dp[i][1].fir = cnt2[i][1] + dp[i-1][1].fir ;
    for(register int i=2; i<=n; i++)
        for(register int j=2; j<=n; j++) dp[i][j].fir = min(cnt2[i][j]+dp[i][j-1].fir,cnt2[i][j]+dp[i-1][j].fir) ;
    for(register int i=1; i<=n; i++) dp[1][i].se = cnt5[1][i] + dp[1][i-1].se ;
    for(register int i=1; i<=n; i++) dp[i][1].se = cnt5[i][1] + dp[i-1][1].se ;
    for(register int i=2; i<=n; i++)
        for(register int j=2; j<=n; j++) dp[i][j].se = min(cnt5[i][j]+dp[i][j-1].se,cnt5[i][j]+dp[i-1][j].se) ;
    cout << min(dp[n][n].fir,dp[n][n].se) << endl ;
#undef fir
#undef se
}
signed main() {
    n = In() ;
    for(register int i=1; i<=n; i++)
        for(register int j=1; j<=n; j++) {
            int x = In() ;
            if(x == 0) return puts("1") , 0 ;
            cnt2[i][j] = ret(x,2) ;
            cnt5[i][j] = ret(x,5) ;
        }
    return Ot() , 0 ;
}