0w1

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