Codeforces #308 Div2 E. Vanya and Brackets

字句解析系か。
http://codeforces.com/contest/552/problem/E

問題

1桁の整数と"+"と"*"で構成された数式が与えられる。
ここで一組だけ括弧を追加し、数式の値を最大化せよ。

なお、"*"の登場回数は最大15個である。

解法

括弧を使うとすると、1*(2+3+4+5)*6のように乗算演算子の周辺に使うのが良い。
1+(2*3+4*5)+6のように"+"で囲まれた部分を囲っても値は増えない。

"*"の数は限られているので、括弧の位置を*の周辺と限定して総当たりし、最大値を求めればよい。

int L;
string S;

ll getval(vector<ll> v,vector<int> op) {
	int i;
	vector<ll> v2;
	v2.push_back(v[0]);
	FOR(i,v.size()-1) {
		if(op[i]==0) v2.push_back(v[i+1]);
		else v2.back()*=v[i+1];
	}
	
	ll ret=0;
	FORR(r,v2) ret+=r;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	L=S.size();
	
	vector<int> cand;
	for(i=0;i<L;i+=2) if(i==0 || i==L-1 || (i>0 && S[i-1]=='*')||(i<L-1&&S[i+1]=='*')) cand.push_back(i/2);
	
	ll ma=0;
	FOR(y,cand.size()) FOR(x,y+1) {
		vector<ll> v[3];
		vector<int> op[3];
		FOR(i,L) {
			if(i<cand[x]*2) j=0;
			else if(i<=cand[y]*2) j=1;
			else j=2;
			
			if(i%2) op[j].push_back(S[i]=='*');
			else v[j].push_back(S[i]-'0');
		}
		v[0].push_back(getval(v[1],op[1]));
		copy(v[2].begin(),v[2].end(),back_inserter(v[0]));
		copy(op[2].begin(),op[2].end(),back_inserter(op[0]));
		
		ma=max(ma,getval(v[0],op[0]));
	}
	cout<<ma<<endl;
	
}

まとめ

アプローチは単純だけど若干面倒だね。
evalが使える言語だとラクかもと思ったけどTLEが怖いな。