yukicoder : No.10 ＋か×か

これも割とすんなり。
http://yukicoder.me/problems/29

問題

N個の整数A[i]がある。
ここで、A[0]、A[1]、…、A[N-1]の間に"＋"か"×"を挟んで数式を作り、その結果がTotalとなるようにしたい。
なお、数値の演算順は一般的な数式と異なり、常に左結合である。

条件を満たす記号群のうち、辞書順最小のものを答えよ。

解法

前から順にDFSしていき、先に"＋"を入れ、次に"×"を入れて条件を満たす数式ができるか探索すればよい。
このままやると最悪O(2^N)通り組み合わせが生じてTLEするが、「先頭i個の記号を定めた結果が数値Vとなった場合、残りの記号は一度探索したけどダメだった」という情報を記憶しておき、同じ探索を繰り返さないようにすると良い。

int N,T;
int A[51];
int dp[51][100100];
string S;

void dfs(int cur,int v) {
	if(v>T) return;
	if(cur==N) {
		if(v==T) {
			cout << S <<endl;
			exit(0);
		}
		return;
	}
	if(dp[cur][v]) return;
	dp[cur][v] = 1;
	
	S+='+';
	dfs(cur+1,v+A[cur]);
	S.erase(S.size()-1);
	S+='*';
	dfs(cur+1,v*A[cur]);
	S.erase(S.size()-1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	FOR(i,N) cin>>A[i];
	
	dfs(1,A[0]);
}

まとめ

数値の上限がわかっているおかげで、メモ化再帰ができるね。