1103 Integer Factorization (30分) [dfs]

factorization  因子分解

1、首先判斷是dfs深度優先搜尋。

2、打個表，把從0-sqrt(n)之間數的平方值都存入

3、構思dfs（模闆）

>1   思考每次操作後改變的，将變量作為參數。

那麼這裡的變量有  目前處理的值，值的個數，值的P次方總和，值的總和

>2  得到答案的情況

>3  剪枝的情況

>4 處理，要or不要

4、題目中要求的序列大小  直接從大到小dfs即可。

#include<bits/stdc++.h>
using namespace std;
vector<int> fac;
int n,k,p;
void init(){
	for(int i=0;pow(i,p)<=n;i++){
		fac.push_back(pow(i,p));
	}
}
vector<int> temp,ans;
int maxsum=-1;//要求 
/*每次的變量：目前處理的值index
 			  目前的P和sumP
			  目前的個數nowK 
			  目前的和sum 
*/ 
void dfs(int index,int nowK,int sumP,int sum){
	//答案 
	if(nowK==k&&sumP==n){
		if(sum>maxsum){
			ans=temp;maxsum=sum;
		}
		return;
	}
	//非法，剪枝 
	if(nowK>k||sumP>n||index<1) return;
	//填入，選或不選
	temp.push_back(index);
	dfs(index,nowK+1,sumP+fac[index],sum+index);
	temp.pop_back(); 
	dfs(index-1,nowK,sumP,sum);
}
int main(){
	cin>>n>>k>>p;
	init();
	dfs(fac.size()-1,0,0,0);
	if(maxsum==-1) printf("Impossible");
	else{
        printf("%d =",n);
        for(int i=0;i<ans.size();i++){
            printf(" %d^%d",ans[i],p);
            if(i!=ans.size()-1) printf(" +");
        }
    }
    return 0;
	
}