PAT_A_1103 Integer Factorization

题意：给定总和n，数字个数k，指数p，求由给定的数字个数的数的p次方的和为n（即总和），若有多种情况，则找到最大的子序列

思路：首先如果index的指数次方小于等于n，把1到index的指数次方加入到v数组中，然后从v.size()-1~1进行枚举，从最大的开始枚举，也属于一种DFS深度搜索+剪枝，首先从最大的根节点开始搜索，查找当前的总和的情况，小于则保持当前的index，大于则需要向子树搜索，寻找更小的孩子节点；

代码：

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
vector<int> v, tempans, ans;
int n = 0, k = 0, p = 0, maxsum = -1;
void init() {//把index的p次方依次压入数组，表示要1-index中找到和为n，index和最大的情况
	int temp = 0, index = 1;
	while (temp <= n) {
		v.push_back(temp);
		temp = pow(index, p);
		index++;
	}
}
void dfs(int index, int temk, int temsum, int facsum) {
	if (temk == k) {
		if (temsum == n && facsum > maxsum) {
			ans = tempans;
			maxsum = facsum;
		}
		return;//剪枝，节点数满足，无论是不是比之前的情况更优都要退出了
	}
	while (index <= n) {
		if (temsum + v[index] <= n) {
			tempans[temk] = index;
			dfs(index, temk + 1, temsum + v[index], facsum + index);
		}
		if (index == 1)return;//已经到结尾了
		index--;//继续往下面找
	}
}
int main() {
	cin >> n >> k >> p;
	tempans.resize(k);
	init();
	dfs(v.size() - 1, 0, 0, 0);
	if (maxsum == -1) {
		printf("Impossible\n");
	}
	else {
		printf("%d = ", n);
		for (int i = 0; i < ans.size(); i++) {
			printf("%d^%d%s", ans[i], p, i == ans.size() - 1 ? "\n" : " + ");
		}
	}
	system("pause");
	return 0;
}