1103 Integer Factorization

题目大意

给三个正整数N、K、P，将N表示成K个正整数的P次方和，其中，这K个正整数必须递减排列，允许重复，如果有多种方案，选择底数n1+…+nk最大的方案，如果还有多种方案，选择底数序列的字典序最大的方案。

---

思路解析

穷举法暴力模拟，为了避免超时，一般都把待选数放到一个数组里，而不是每次重新计算。我一开始以为给定第一个数的大小作为上界，剩余的数字在界内递归选择，第一次找到sum == n && deep == k的就是结果，然而会有超时，成功被PAT数据gank，所以以后还是乖乖的按照常规做法搞吧。

---

示例代码

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int n, k, p,maxsum;
vector<int> v, res,res2;//v是×n次方后的待选数字，res存放临时结果
void dfs(int index,int sum,int facsum, int deep) {
	if (sum == n) {
		if (facsum > maxsum && deep == k) {
			maxsum = facsum;
			res2 = res;
		}
		res.pop_back();
		return;
	}
	for (int i = index; i > 0; i--) {
		if (sum + v[i] <= n && deep + 1 <= k) {
			res.push_back(i);
			dfs(i, sum + v[i], facsum + i, deep + 1);
		}
	}
	if (res.size() > 0)  res.pop_back();
}
int main() {
	scanf("%d %d %d", &n, &k, &p);
	for (int i = 0; pow(i, p) <= n; i++)
		v.push_back(pow(i, p));//初始化数组v
	dfs(v.size() - 1, 0, 0, 0);
	if (res2.size() != k) {
		printf("Impossible\n");
	}
	else{
		printf("%d = %d^%d", n, res2[0], p);
		for (int i = 1; i < res2.size(); i++) 
			printf(" + %d^%d", res2[i], p);
	}
	return 0;
}