1.题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805364711604224
给出正整数N,K,P，求N由K个整数的分别的P次方的和的情况，如果有多种情况则选择底数和最大的方案。
举例：169 5 2
输出：159=6^ 2 + 6^ 2+6^ 2+6^ 2+5^ 2
2.思路
（1）开一个vector数组fac存0^ p ,1^ p… i ^ p.
（2）DFS：
分叉口：利用DFS对fac[index]进行选择，有“选”与“不选”两种选择，如果不选，则把问题转化为对fac[index]进行选择；如果选择，由于每个数字可以重复选择即下一次还能选择fac[index]。
递归边界：2个return，第一个满足sum == N且nowK==k成立时则找到一个满足条件的序列——记住为了找出多方案的最优情况，需要判断底数之和facSum是否比一个全局记录的最大底数之和maxFacSum更大，更大则更新。
第二个return是底数之和大于N或底数个数大于K就不阔能出答案了，马上return。
（3）为了让结果能够保证字典序大的序列优先被选中，让index从大到小递减来遍历，这样总是能先选中fac中较大的数。
3.代码
#include<cstdio> #include<iostream> #include<vector> #include<algorithm> using namespace std; const int maxn=30; vector<int>fac,ans,temp;//fac记录i^p int n,k,p,maxFacSum=-1; int pinfang(int x){ int ans=1; for(int i=0;i<p;i++){ ans*=x; } return ans; } //init函数预处理fac数组，注意把0也存进去 void init(){ int i=0,temp1=0; while(temp1<=n){ fac.push_back(temp1); temp1=pinfang(++i); } } void DFS(int index,int nowK,int sum,int facSum){ if(sum==n&&nowK==k){//找到一个满足的序列 if(facSum>maxFacSum){ ans=temp; maxFacSum=facSum;//更新最大底数之和 } return; } if(sum>n||nowK>k) return;//不会产生答案，直接返回 if(index-1>=0){//fac[0]不需要选择，从大到小 temp.push_back(index); DFS(index,nowK+1,sum+fac[index],facSum+index); temp.pop_back(); DFS(index-1,nowK,sum,facSum); } } int main(){ scanf("%d%d%d",&n,&k,&p); init(); DFS(fac.size()-1,0,0,0);//从fac的最后一位开始往前搜索 if(maxFacSum==-1) printf("Impossible\n"); else{ printf("%d = %d^%d",n,ans[0],p); for(int i=1;i<ans.size();i++) printf(" + %d^%d",ans[i],p); } system("pause"); }
4.注意
（1）多方案时判断是否更优的做法的时间复杂度最好是O（1），否则容易超时。因此必须在DFS的参数中记录当前底数之和facSum，避免在找到一组解时计算序列的底数之和。
（2）和（1）一样，不要在找到一组解时才判断vector型的temp和ans数组的字典序，而应该让index从大到小进行选择，这样fac[index]大的就会相对早地被选中。
