1.题目要求把一个数转化为固定项数的p次方数相加。
2.根据题目的特点，n的最大值不超过400，可以使用深度遍历搜索答案
3.加入限制条件进行剪枝，如i的p次方不能大于n-k+1，因为剩下的数至少均为1，剩下还需要k-1个数需要进行分配，每个数至少分配为1，共k-1，所以i的p次方最大只能为n-（k-1）=n-k+1，而最大值不能超过上一次分配的。
The K-P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K-P factorization of N for any positive integers N, K and P.
Input Specification:
Each input file contains one test case which gives in a line the three positive integers N (<=400), K (<=N) and P (1<P<=7). The numbers in a line are separated by a space.
Output Specification:
For each case, if the solution exists, output in the format:
N = n1^P + … nK^P
where ni (i=1, … K) is the i-th factor. All the factors must be printed in non-increasing order.
Note: the solution may not be unique. For example, the 5-2 factorization of 169 has 9 solutions, such as 122 + 42 + 22 + 22 + 12, or 112+ 62 + 22 + 22 + 22, or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen — sequence { a1, a2, … aK } is said to be larger than { b1, b2, … bK } if there exists 1<=L<=K such that ai=bi for i<L and aL>bL
If there is no solution, simple output “Impossible”.
Sample Input 1:
169 5 2
Sample Output 1:
169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2
Sample Input 2:
169 167 3
Sample Output 2:
Impossible
AC代码：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
void dfs(int n, int count, int p,int preNum, vector<int>&ans,int ansSum, vector<pair<int,vector<int>>>&totalAns, vector<vector<int>>&num)
{
if (n == 0 && count == 0)
{
totalAns.push_back({ansSum, ans});
}
else if ((n == 0 && count != 0) || (n != 0 && count == 0))
return;
else
{
for (int i = min(n – count+1,preNum); i >= 1; i–)
{//进行剪枝
if (num[i][p – 1] != -1 && num[i][p – 1]<=n-count+1)
{
ans.push_back(i);
ansSum += i;
dfs(n – num[i][p – 1], count – 1, p,i, ans,ansSum, totalAns, num);
ansSum -= i;
ans.pop_back();
}
}
}
}
bool cmp(const pair<int, vector<int>>&a, const pair<int, vector<int>>&b)
{
if (a.first > b.first)
return true;
else if (a.first == b.first)
{
for (int i = 0; i < a.second.size(); i++)
{
if (a.second[i] > b.second[i]) return true;
else if (a.second[i] < b.second[i]) return false;
}
}
else return false;
}
int main(void)
{
int n, k, p;
cin >> n >> k >> p;
vector<vector<int>> num(401, vector<int>(7, 0));
for (int i = 1; i < 401; i++)
{
num[i][0] = i;
for (int j = 1; j < 7; j++)
{
if (num[i][j – 1] == -1) num[i][j] = -1;
else
{
num[i][j] = num[i][j – 1] * i;
if (num[i][j] > 400) num[i][j] = -1;
}
}
}
vector<int> ans(0);
vector<pair<int,vector<int>>> totalAns(0);
int ansSum = 0;
dfs(n, k, p,n, ans,ansSum, totalAns, num);
sort(totalAns.begin(), totalAns.end(), cmp);
if (totalAns.size() != 0)
{
cout << n << " = ";
for (int i = 0; i < totalAns[0].second.size(); i++)
{
cout << totalAns[0].second[i] << "^" << p;
if (i != totalAns[0].second.size() – 1)
{
cout << " + ";
}
}
cout << endl;
}
else
{
cout << "Impossible" << endl;
}
return 0;
}
[/c]