【算法】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;
}