题意:给定一个数n，问是否有k个数字，使得他们的p次方和等于数n，若有输出表达式，否则输出Impossible
tip:DFS + 剪枝
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int n,k,p,maxlen=0;
int power[403]={0};
vector<int >ans,temp;
void init()
{
for(int i=0;i<403;++i)
power[i]=(int)pow(i,p);
}
void dfs(int t,int sum,int count) {
if(t>0)
temp.push_back(t);
if(sum>n||count>k)//剪枝
return ;
if(sum==n&&count==k) {
int t=0;
for(int i=0; i<k; ++i)
t+=temp[i];
if(t>maxlen) {//比较元素和
maxlen=t;
ans=temp;
} else ans=temp;//元素和相等时比较序列大小，肯定是后来的大
return;
}
for(int i=t; i<pow(1.*n/k+1,1.2/p)+1; ++i) {
if(i>0) {
dfs(i,sum+power[i],count+1);
temp.pop_back();
}
}
}
int main() {
cin>>n>>k>>p;
init();
dfs(0,0,0);
if(ans.size()) {
cout<<n<<" = "<<ans[ans.size()-1]<<"^"<<p;
for(int i=ans.size()-2; i>=0; --i)
printf(" + %d^%d",ans[i],p);//逆序输出即为降序
cout<<endl;
} else cout<<"Impossible\n";
return 0;
}