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;}新闻热点
疑难解答
