1103 Integer Factorization (30分)

#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
int N, K, P;
vector<int> res, temp;
int factorSum = 0;
int ans[401];
void dfs(int i, int item, int curSum, int curFactorSum) {
	if (item == K) {
		if (curSum == N && curFactorSum > factorSum) {
			res = temp;
			factorSum = curFactorSum;
		}
		return;
	}
	while (i > 0) {
		if (curSum + ans[i] <= N) {
			temp.push_back(i);
			dfs(i, item + 1, curSum + ans[i], curFactorSum + i);
			temp.pop_back();
		}
		i--;
	}
}
int main() {
	scanf("%d %d %d", &N, &K, &P);
	for (int i = 0;i <= N;i++) {
		ans[i] = pow(i, P);
	}
	int start = 0;	//找到dfs开始的位置，很关键
	while (ans[start] <= N)
		start++;
	dfs(start, 0, 0, 0);
	if (res.empty()) {
		printf("Impossible");
	}
	else {
		printf("%d = ", N);
		for (int i = 0;i < res.size();i++) {
			if (i != 0)
				printf(" + ");
			printf("%d^%d", res[i], P);
		}
	}
}