Codeforces #205, C : Find Maximum

問題文

http://codeforces.com/contest/353/problem/C

概要

N 項からなる数列 a がある。
関数 f を次のように定める。
　
　ただし bit(i) は x の i bit 目が立っているときに 1 になる関数
x が m 以下のとき、f(x) の最大値を求めよ。

解法

x の上の桁から決めていくとします。
このとき、m 未満となることが確定していれば、それ以降の桁は任意に決められます。
そうでないとき、bit( m ) が 1 の桁でしか 1 にできません。
bit( m ) が 1 の桁を 0 にすると m 未満が確定します。

以上から、次のような DP を考えることができます。
　dp[ i 桁考慮した ][ m 未満かどうか ] := 最大の f( x )

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()

const int INF = INT_MAX / 2;

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	string s;
	cin >> s;

	reverse( ALL( as ) );
	reverse( ALL( s ) );

	VVI dp( n + 1, VI( 2, -INF ) );
	dp[0][0] = 0;
	REP( i, 0, n )
	{
		REP( j, 0, 2 )
		{
			dp[ i + 1 ][ j || s[i] == '1' ] = max( dp[ i + 1 ][ j || s[i] == '1' ], dp[i][j] );
			if ( j || s[i] == '1' )
			{
				dp[ i + 1 ][j] = max( dp[ i + 1 ][j], dp[i][j] + as[i] );
			}
		}
	}

	cout << *max_element( ALL( dp.back() ) ) << endl;

	return 0;
}