本题是典型的DFS+剪枝

我对DFS有了更深的认识：整个过程就是一片森林(根节点不唯一)的生长，到了界限就得到结果并返回或者得不到结果也返回，DFS的参数存放的是所有需要积累的变量。

提示：

1. 最外层的while或者for可以看成是一个平行的循环过程——树的不同根。

2. 主函数不再循环调用DFS。

3. 剪枝可以放在DFS函数内部的首段，也可以作为进入DFS的条件。

非AC代码，一个测试点超时原因待查明。

#include<cstdio>
#include<iostream>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>using namespace std;const int maxn = 210;int v[maxn];int N,K,P;int maxFacSum = -1;int tempK,tempFacSum,tempN;vector<int> ansV;
vector<int> tempV;void DFS(int i,int tempK,int tempN,int tempFacSum){if(tempK==K){if(tempN==N&&tempFacSum>maxFacSum){ansV = tempV;maxFacSum = tempFacSum;}return;}for(int j=i;j>0;j--){if(v[j]<=N-tempFacSum){tempV[tempK] = j; DFS(j,tempK+1,tempN+v[j],tempFacSum+j); }}
} int main(){cin>>N>>K>>P;int i;for(i=0;i<maxn;i++){if(pow(i,P)<=N){v[i] = pow(i,P);}else break;}tempV.resize(K);DFS(i-1,0,0,0); if(maxFacSum == -1)printf("Impossible\n");else{printf("%d = ",N);for(int i=0;i<K;i++){printf("%d^%d%s",ansV[i],P,i==K-1?"\n":" + ");}}return 0;
}