（dfs深度优先搜索）
思路
先把i从0开始所有的i的p次方的值存储在v[i]中，直到v[i] > n为止。(如果在递归过程中计算次方，会做很多重复工作，很浪费时间。) 然后深度优先搜索，记录当前正在相加的index（即v[i]的i的值），当前的总和tempSum，当前K的总个数tempK，以及因为题目中要求输出因子的和最大的那个，所以保存一个facSum为当前因子的和，让它和maxFacSum比较，如果比maxFacSum大就更新maxFacSum和要求的ans数组的值。 在ans数组里面存储因子的序列，tempAns为当前深度优先遍历而来的序列，从v[i]的最后一个index开始一直到index == 1，因为这样才能保证ans和tempAns数组里面保存的是从大到小的因子的顺序。 一开始maxFacSum == -1，如果dfs后maxFacSum并没有被更新，还是-1，那么就输出Impossible，否则输出答案。 剪枝： 1.tempK==K但是tempSum!=n的时候需要剪枝 2.在枚举的时候，按顺序枚举，上界或者下界可进行剪枝 3.当且仅当tempSum + v[index] <= n时，进行下一层的DFS，而不要进入下一层DFS发现不满足条件再返回，这样开销会比较大 4.每次temv的push_back、pop_back都需要重新分配内存空间，比较耗时，由于答案的序列长度是确定的，可以将ans序列初始化为定长的，这样在递归的过程中就不需要push、pop; pow的计算结果可以保存下来，以免重复计算，耗用多余的时间
坑
1.要先存好次方计算后的值，避免递归时重复计算。 2.直接利用maxsum来判断是否有解，通过设初值为负数。无需额外建立标记判断。 3.倒着递归，从大数开始判断。
AC代码
/*第二次写*/
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
int n, k, p, maxsum = -1;
vector<int>num, ans, bestans;
void DFS(int index, int result, int sum, int x) {
if (result == n && x == k) {
if (sum > maxsum) {
bestans = ans;
maxsum = sum;
}
else if (sum == maxsum) {
int i = k - 1;
while (i >= 0 && ans[i] == bestans[i])i--;
if (ans[i] > bestans[i])bestans = ans;
}
return;
}
else if (index < 0 || x >= k || result >= n)return;
if (result + num[index] <= n) {
ans[x] = index + 1;
DFS(index, result + num[index], sum + index, x + 1);
}
DFS(index - 1, result, sum, x);
}
int main() {
int i, a, b;
scanf("%d%d%d", &n, &k, &p);
ans.resize(k); bestans.resize(k);
for (i = 1; i <= n; i++) {
a = pow(i, p);
if (a > n)break;
num.push_back(a);
}
DFS(num.size() - 1, 0, 0, 0);
if (maxsum < 0)printf("Impossible");
else {
printf("%d = %d^%d", n, bestans[0], p);
for (i = 1; i < k; i++)printf(" + %d^%d", bestans[i], p);
}
return 0;
}
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAX 500
int n, k, p, maxsum = -1;
vector<int>v;
vector<int>solution, maxsolution;
void optmax() {
int i = 0;
while (solution[i] == maxsolution[i])i++;
if (solution[i] > maxsolution[i])
maxsolution = solution;
}
void DFS(int index, int count, int ans, int sum) {
if (count == k && ans == n) {
if (maxsum < sum) {
maxsum = sum;
maxsolution = solution;
}
else if (maxsum == sum) optmax(); //此处可以不用判断相等情况，也能AC。
return;
}
if (index == 0 || ans > n || count >= k)return;
if (ans + v[index] <= n) {
solution.push_back(index);
DFS(index, count + 1, ans + v[index], sum + index);
solution.pop_back();
}
DFS(index - 1, count, ans, sum);
}
int main() {
scanf("%d%d%d", &n, &k, &p);
int temp = 0, index = 1;
while (temp <= n) {
v.push_back(temp);
temp = pow(index, p);
index++;
}
DFS(v.size() - 1, 0, 0, 0);
if (maxsum < 0)printf("Impossible");
else {
printf("%d = %d^%d", n, maxsolution[0], p);
for (int i = 1; i < k; i++)
printf(" + %d^%d", maxsolution[i], p);
}
return 0;
}
另
如果改成正着来，测试点5就超时了...实在想不通是什么回事，希望走过路过的大神们帮我看看，感激不尽！！！ （我想应该是从大数开始比较容易到达边界，减少了递归次数）
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAX 500
int n, k, p, maxsum = -1;
vector<int>v;
vector<int>solution, maxsolution;
bool cmp(int a, int b) { return a > b; }
void optmax() {
int i = 0;
while (solution[i] == maxsolution[i])i++;
if (solution[i] > maxsolution[i])
maxsolution = solution;
}
void DFS(int index, int count, int ans, int sum) {
if (count == k && ans == n) {
if (maxsum < sum) {
maxsum = sum;
maxsolution = solution;
}
else if (maxsum == sum) optmax();
return;
}
if (index >= v.size() || ans > n || count >= k)return;
if (ans + index <= n) {
solution[count] = index;
DFS(index, count + 1, ans + v[index], sum + index);
}
DFS(index + 1, count, ans, sum);
}
int main() {
scanf("%d%d%d", &n, &k, &p);
solution.resize(k);
int temp = 0, index = 1;
while (temp <= n) {
v.push_back(temp);
temp = pow(index, p);
index++;
}
DFS(1, 0, 0, 0);
if (maxsum < 0)printf("Impossible");
else {
printf("%d = %d^%d", n, maxsolution[k - 1], p);
for (int i = k - 2; i >= 0; i--)
printf(" + %d^%d", maxsolution[i], p);
}
return 0;
}
