CFR 550 C. Divisibility by Eight ( DP )
Problem - 550C - Codeforces
題意:
給一個大數,求任意刪除數字,使其為 8 的倍數。
解法:
如果有 0,那麼就變 0。否則基於 8 的倍數只與後三位有關的性質,進行動態規劃,紀錄 0 至 999 的數是否可以達到。
string _seq; void init(){ cin >> _seq; } vi seq; int zero_cnt; void preprocess(){ seq.resize( _seq.size() ); for( int i = 0; i < seq.size(); ++i ) seq[ i ] = _seq[ i ] - '0'; zero_cnt = count( seq.begin(), seq.end(), 0 ); } void solve(){ if( zero_cnt > 0 ){ cout << "YES" << endl; cout << 0 << endl; return; } vi dp( 1000 ); dp[ 0 ] = 1; for( int i = 0; i < seq.size(); ++i ) for( int j = 1000 - 1; j >= 0; --j ){ if( j * 10 + seq[ i ] >= 1000 ) continue; dp[ j * 10 + seq[ i ] ] |= dp[ j ]; } for( int i = 8; i < 1000; i += 8 ) if( dp[ i ] ){ cout << "YES" << endl; cout << i << endl; return; } cout << "NO" << endl; }