【算法】P1010 [NOIP1998 普及组] 幂次方 解题代码

dfs记忆化搜索没什么可说的

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <vector>
#define endl '\n'

using namespace std;

unordered_map<int, string> mp;

int n;

string join(vector<string> &strs, string split){
	string t;
	for (int i = strs.size() - 1; i >= 0; i--)
	{
		t += strs[i] + split;
	}
	t.pop_back();
	return t;
}

string dfs(int n){
	int k = n;
	int i = 0;
	if (n == 0) return "2(0)";
	if (n == 1) return "2";
	
	vector<string> vec;
	while (k){
		if (k % 2){
			if (!mp.count(i)){
				vec.push_back(dfs(i));
			}else{
				vec.push_back(mp[i]);
			}
		}
		i ++;
		k /= 2;
	}
	string s = join(vec, "+");
	mp[n] = "2(" + s + ")";
	return "2(" + s + ")";
}

int main(){
	cin.tie(0), cout.tie(0);
	cin >> n;
	string ans = dfs(n).substr(2);
	ans.pop_back();
	cout << ans << endl;
	return 0;
}