地产大亨Q先生临终的遗愿是：拿出100万元给X社区的居民抽奖，以稍慰藉心中愧疚。 麻烦的是，他有个很奇怪的要求：
100万元必须被正好分成若干份（不能剩余）。每份必须是7的若干次方元。 比如：1元, 7元，49元，343元，…
相同金额的份数不能超过5份。
在满足上述要求的情况下，分成的份数越多越好！
请你帮忙计算一下，最多可以分为多少份？注意：只需要填写一个整数，就是分成的份数，不要填写任何多余的内容。比如说明文字。
分析: dfs 因为相同金额可以有5份 所以递归的时候有两种情况 1.当前次方元+1 visit[step]+1 2.下一次方元+1 visit[step+1]+1 通过份数不能超过5份和金额不能大于100万条件退出递归
#include <iostream> #include <cmath> using namespace std; int count = 0; int visit[10] = {0}; int num; void dfs(int step,int count) { //step代表7的几次方 if(visit[step] > 5) { //相同金额的份数不能超过5份 return; } if(count > 1000000) { return; } else if(count == 1000000){ num = 0; for(int i = 0; i < 10; i++) { num += visit[i]; } cout<< num; exit(0); } count += pow(7,step); visit[step]++; dfs(step, count); //两种路 visit[step]+1 dfs(step+1, count); //visit[step+1]+1 visit[step]--; count -= pow(7,step); } int main() { dfs(0,0); return 0; }