PAT A1103 Integer Factorization　——如果你愿意一层一层一层的剥开我的心～

PAT A1103 Integer Factorization　——如果你愿意一层一层一层的剥开我的心～

PAT A1103 Integer Factorization

• 此题简单的描述不禁使我浮想联翩，质因数分解啦，几次方再求和怎么处理啦，遍历的范围和定位啦。。。最后终于步入正轨，应该先把N范围以内的K次方先放到数组里边备选，于是就变成了从一个有序数组中挑选M个数字使之总和=N(不是连续子序列有点可惜)。
• 开始想用hash数组定位K次方数，从N开始倒着循环，搞到一半发现每个数都是可以取多次的，我这一个循环显然不行　——感觉变成了完全背包了呦，可这个包我暂时还不会
• 于是偷看了书上的，居然用的dfs。。。并且有理有据，使人信服。对于每个位置idx都有选和不选两种情况，if选，呢么idx放入序列数组，同时增加个数、次方总和与序列总和，并把问题仍然扔给当前的idx(因为选了她，所以下次仍由她来决定)；if不选，先要把刚才push进去的吐出来(因为是逐层向下并且逐层返回的，所以dfs之后pop的就是dfs之前push的)，然后直接把问题丢给前一个位置idx-1,因为没有放，所以那几个数据都不用增加，原包装转手，后面的事情由idx-1去处理
• 最后一小点是Impossible并不能由vans.size()==0来判断，起码应该是!=M

#include<iostream>
#include<vector>
#include<cmath>using namespace std;vector<int> v,vans,vtmp;
int max_fsum = -1;
int N,M,K;void dfs(int idx,int cnt,int sum,int facsum){if(cnt == M && sum == N){if(facsum > max_fsum){max_fsum = facsum;vans = vtmp;}return;}if(cnt > M || sum > N) return;if(idx >= 1){vtmp.push_back(idx);dfs(idx,cnt + 1,sum + v[idx],facsum + idx);vtmp.pop_back();dfs(idx - 1,cnt,sum,facsum);}
}int main(){scanf("%d %d %d",&N,&M,&K);int tmp = 0;for(int i = 1;tmp <= N;i ++){v.push_back(tmp);tmp = pow(i,K);} dfs(v.size() - 1,0,0,0);if(max_fsum == -1){printf("Impossible");return 0;} printf("%d = ",N);for(int i = 0;i < vans.size();i ++){printf("%d^%d",vans[i],K);if(i < vans.size() - 1) printf(" + ");}return 0;
}