UVA 1374: Power Calculus (TLE version. how to improve?)

1374.cpp

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstdlib>
using namespace std;

#define fori(i,s,e) for(int i = s; i < ((int)e); i++)
#define allof(s) (s).begin(), (s).end()

// 2 log n strategy (just for intuitive bound on the max size of answer):
// build all x^(2^k)
// n = 2^k1 + 2^k2 + ... + 2^ka (binary repr.)

vector<int> state;
bool dfs(int depth, int target) {
	if (depth == 0) {
		return state.back() == target;
	}

	// VERY SLOW. how to optimize / prune?
	for (size_t i = 0; i < state.size(); i++) {
		for (size_t j = i; j < state.size(); j++) {
			state.push_back(state[i] + state[j]);
			if (dfs(depth - 1, target)) return true;
			state.pop_back();

			state.push_back(abs(state[i] - state[j]));
			if (dfs(depth - 1, target)) return true;
			state.pop_back();
		}
	}
	return false;
}

int solve(int x) {
	if (x == 1) return 0;
	int depth = 1;
	state.clear();
	state.push_back(1);
	while (!dfs(depth, x)) depth++;
	return depth;
}

int main() {
	int x;
	while (cin >> x, x) {
		cout << solve(x) << "\n";
	}
}