【PAT】1103 Integer Factorization (30 分)

大的index开头，

当前方案还从index开始，下一方案从index-1开始。

当前方案下一个还可以是index

#include 
using namespace std;
int n,k,p;
#define maxn 410
vector t;
void initTablet(){
    for(int i=0;pow(i,p)<=n;i++){
        t.push_back(pow(i,p));
    }
}

vector this_ans,ans;
int max_fac_sum=-1;
void dfs(int root,int sum,int fac_sum,int cnt){
    if(cnt==k){
        if(sum==n && fac_sum>max_fac_sum){
            ans=this_ans;                         //vector的好处：互相赋值
            max_fac_sum=fac_sum;
        }
        return;
    }
    while(root>=1){
        if (sum + t[root] <= n){
            this_ans[cnt]=root;
            dfs(root, sum + t[root], fac_sum + root, cnt + 1);
        }
        root--;
    }
}
int main(){
      cin>>n>>k>>p;
      initTablet();
      this_ans.resize(k);
      dfs(t.size()-1,0,0,0);//n太大了,利用最大size()可以放小很多

      if(max_fac_sum==-1){//没有解决方案时
          cout<<"Impossible";
          return 0;
      }
      cout<