【1103】Integer Factorization (30分)【DFS】

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
//DFS，注意生成分支：是否选择index
int n,k,p,maxFacSum=-1;//n=k个(数i^p)
vector<int> v,ans,tempAns;
//ans数组存储因子的序列，tempAns为当前DFS来的序列,init把i从0开始所有的i的p次方的值存储在v[i]中
void init(){
  int temp=0,index=1;
  while(temp <=n){
    v.push_back(temp);
    temp=pow(index,p);
    index++;
  }
}
/*    
index为当前正相加的v[i]的i
tempSum当前的总和
tempK当前K的总个数
facSum为当前因子和
*/
void dfs(int index,int tempSum,int tempK,int facSum){
  if(tempK==k&&tempSum==n){ //有结果
    if(facSum >maxFacSum){ //剪枝1
      ans=tempAns;
      maxFacSum=facSum;//更新当前的因子和
    }
    return;
  }
  if(tempK>k || tempSum>n)  return;//无结果
  if(index >= 1){ //生成分支
    tempAns.push_back(index);//选择index
    dfs(index,tempSum+v[index],tempK+1,facSum+index);
    tempAns.pop_back();
    dfs(index-1,tempSum,tempK,facSum);//不选择index
  }
}
/*剪枝：
1.  tempK==K但是tempSum!=n的时候需要剪枝
2.  在枚举的时候，按顺序枚举，上界或者下界可进行剪枝
*/
int main(){   
  scanf("%d%d%d",&n,&k,&p);
  init();
  dfs(v.size()-1 ,0,0,0);
  //从v[i]末尾往前遍历，保证ans和tempAns数组保存的是从大到小的因子的顺序
  if(maxFacSum == -1) {
    printf("Impossible");
    return 0;
  }//开始maxFacSum == -1，如果dfs后maxFacSum仍为-1，则输出Impossible，否则输出答案
  printf("%d = ",n);
  for(int i=0;i<ans.size();i++) {
    if( i != 0) printf(" + ");//细节
    printf("%d^%d",ans[i],p);  
  }  
  system("pause");
    return 0;   
}