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; }