思路
本题是深搜的一个应用：排列组合，选取给定的序列中的部分数字（可重复选择）使得满足给定条件。放到本题中：给定序列，从1到x（x是第一个p次大于等于n的数），满足条件：每项的p次和为n.
组合按照非增序排列，若有多组，选择和最大的一组结果。若结果仍不唯一，选择两组数字中，第一个不相等元素中较大的那个组合。例如9 9 7 6；9 9 7 3；，第一个不相等的元素为6和3 选择6 的元素的那个组合。
同时，考虑到pow运算多次重复，可以使用打表的技巧，以减少用时，通过样例5。
样例四的数据应该类似 23 1 1.
和力扣39 40 一样，建议没思路的同学可以先做力扣
代码
#include <bits/stdc++.h>
using namespace std;
int n, k, p;
const int maxn = 403;
int power[maxn];
vector<int> nums, num2;
vector<int> ans;
int maxsum = 0;
void dfs(int len, int target, int idx, int numsum, vector<int>& combine) {
if (idx >= nums.size()) return;
if (len == 0 && target == 0) {
if (numsum >= maxsum) {
ans = combine;
maxsum = numsum;
}
return;
} else if(len == 0 || target == 0) {
return;
}
dfs(len, target, idx + 1, numsum, combine); //no
if (power[nums[idx]] <= target) {
combine.push_back(nums[idx]);
target -= power[nums[idx]];
len -= 1;
numsum += nums[idx];
dfs(len, target, idx, numsum, combine);
numsum -= nums[idx];
len += 1;
target += power[nums[idx]];
combine.pop_back();
}
}
int main() {
cin>>n>>k>>p;
for (int i = 1; i <= n; i++) {
power[i] = pow(i, p);
if (power[i] > n) break;
num2.push_back(i);
}
for (int i = num2.size() - 1; i >= 0; i--) {
nums.push_back(num2[i]);
}
vector<int> combine;
dfs(k, n, 0, 0, combine);
if (ans.size() == 0) {
cout<<"Impossible"<<endl;
return 0;
}
cout<<n<<" =";
for (int i = 0; i < k; i++) {
printf(" %d^%d", ans[i], p);
if (i != k - 1) printf(" +");
}
}
