CFR 2 B. The least round way ( DP )

Problem - 2B - Codeforces
題意：
給 N * N 的矩陣。由左上角出發，走到右下角，求經過的所有數之乘積最少的結尾零個數，以及其中一個方案。
解法：
先考慮整張矩形不存在 0。分別求起點至終點經過的最少 2 因數的數量，和最少 5 因數的數量。取其最小值即是最少零的方法。若存在零，多一個可能最優解，可以直接選它，使答案便 1。

int N;
vvi A;

void init(){
    cin >> N;
    A = vvi( N, vi( N ) );
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < N; ++j )
            cin >> A[ i ][ j ];
}

pii z_pos;
vvi dp2; // minimum count of 2s 
vvi dp5;
vvp pre2;
vvp pre5;

int get2( int x ){
    int res = 0;
    while( x and x % 2 == 0 )
        x /= 2,
        ++res;
    return res;
}

int get5( int x ){
    int res = 0;
    while( x and x % 5 == 0 )
        x /= 5,
        ++res;
    return res;
}

map< pii, char > mpc;

void preprocess(){
    mpc[ pii( 0, 1 ) ] = 'R';
    mpc[ pii( 1, 0 ) ] = 'D';
    z_pos = pii( -1, -1 );
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < N; ++j )
            if( A[ i ][ j ] == 0 )
                z_pos = pii( i, j );
    dp2 = dp5 = vvi( N, vi( N, INF ) );
    pre2 = pre5 = vvp( N, vp( N, pii( -1, -1 ) ) );
    dp2[ 0 ][ 0 ] = get2( A[ 0 ][ 0 ] );
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < N; ++j ){
            if( i + 1 < N and upmin( dp2[ i + 1 ][ j ], dp2[ i ][ j ] + get2( A[ i + 1 ][ j ] ) ) )
                pre2[ i + 1 ][ j ] = pii( i, j );
            if( j + 1 < N and upmin( dp2[ i ][ j + 1 ], dp2[ i ][ j ] + get2( A[ i ][ j + 1 ] ) ) )
                pre2[ i ][ j + 1 ] = pii( i, j );
        }
    dp5[ 0 ][ 0 ] = get5( A[ 0 ][ 0 ] );
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < N; ++j ){
            if( i + 1 < N and upmin( dp5[ i + 1 ][ j ], dp5[ i ][ j ] + get5( A[ i + 1 ][ j ] ) ) )
                pre5[ i + 1 ][ j ] = pii( i, j );
            if( j + 1 < N and upmin( dp5[ i ][ j + 1 ], dp5[ i ][ j ] + get5( A[ i ][ j + 1 ] ) ) )
                pre5[ i ][ j + 1 ] = pii( i, j );
        }
}

void solve(){
    if( not ( dp2[ N - 1 ][ N - 1 ] < dp5[ N - 1 ][ N - 1 ] ) )
        swap( dp2, dp5 ),
        swap( pre2, pre5 );
    if( z_pos != pii( -1, -1 ) and dp2[ N - 1 ][ N - 1 ] > 1 ){
        cout << 1 << endl;
        for( int i = 0; i < z_pos.first; ++i )
            cout << 'D';
        for( int i = 0; i < z_pos.second; ++i )
            cout << 'R';
        for( int i = 0; i < N - 1 - z_pos.first; ++i )
            cout << 'D';
        for( int i = 0; i < N - 1 - z_pos.second; ++i )
            cout << 'R';
        cout << endl;
        return;
    }
    cout << dp2[ N - 1 ][ N - 1 ] << endl;
    stack< char > path;
    for( int x = N - 1, y = N - 1; pre2[ x ][ y ] != pii( -1, -1 ); tie( x, y ) = pre2[ x ][ y ] )
        path.push( mpc[ pii( x - pre2[ x ][ y ].first, y - pre2[ x ][ y ].second ) ] );
    for( ; not path.empty(); path.pop() )
        cout << path.top();
    cout << endl;
}