1103. Integer Factorization (30) 分析：顯然有明顯的遞歸特征：計算n,k,p，實際上只需求出n-i^p,k-1,p；考察回溯； 思路：每次保存該條路徑，直至當前情況的遞歸終止，遞歸終止時，判斷是否滿足題設條件；用vmax記錄最大因子序列和值，cmax記錄當前的最大因子序列和值 幾個小技巧： 1.每次從當前點s開始向后推演因子，而不是從1到n整個進行計算，可以排除重復的數據，降低了遞歸次數，節省了運算時間（讀者可以自己想為什么）； 2.初始值從n(s=n)開始逐漸遞減而不是從1(s=1)開始往后遞增減少了題目要求的非遞增排序過程，即所得的結果已經排好序；
#include <vector>#include <iostream>#include <algorithm>#include <cmath>using namespace std;int vmax=-1,cmax=0;vector<int> cv;vector<vector<int>> ans;bool comp(const vector<int> a,const vector<int> b){ int i=0,len=(a.size()<b.size())?a.size():b.size(); while(i<len&&a[i]==b[i]) ++i; return a[i]>b[i];}void Calculate(int n,int k, int p,int s){ if(n<0||k<0)return; if(n==0&&k==0) { if(vmax<cmax) { ans.clear(); vmax=cmax; ans.push_back(cv); } else if(vmax==cmax) ans.push_back(cv); return; } for(int i=s;i>=1;--i) { cv.push_back(i); cmax+=i; Calculate(n-(int)pow(i*1.0,p*1.0),k-1,p,i); cv.pop_back(); cmax-=i; }}int main(){ int n,k,p; cin>>n>>k>>p; Calculate(n,k,p,n); if(!ans.size()){cout<<"Impossible";return 0;} sort(ans.begin(),ans.end(),comp); cout<<n<<" = "; for(auto it=ans[0].begin();it!=ans[0].end();++it) it!=ans[0].end()-1?cout<<*it<<"^"<<p<<" + ":cout<<*it<<"^"<<p;}新聞熱點
疑難解答
