1103 Integer Factorization （30 分）（C++）

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 = n[1]^P + ... n[K]^P
           

where 

n[i]

 (

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 12​2​​+4​2​​+2​2​​+2​2​​+1​2​​, or 11​2​​+6​2​​+2​2​​+2​2​​+2​2​​, 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 { a​1​​,a​2​​,⋯,a​K​​ } is said to be larger than { b​1​​,b​2​​,⋯,b​K​​ } if there exists 1≤L≤K such that a​i​​=b​i​​ for i<L and a​L​​>b​L​​.

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
           

解题思路：DFS+剪枝

首先存储每个位置的值对应p次方的值，为了节省运算，可以算到该p次方的值大于n就停止运算。

剪枝的情况：所累计的和超过n，加的次数超过k

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int n,k,p,sum = 0,tempsum,tempnum = 0;
std::vector<int> powvalue(405),ans,tempans;
void dfs(int cur,int cnt){
    if(tempnum > n || cnt > k || cur == 0)
        return;
    if(cnt == k && tempnum == n){
        tempsum = 0;
        for(int i = 0; i < tempans.size(); i++)
            tempsum += tempans[i];
        if(tempsum > sum){
            ans = tempans;
            sum = tempsum;
        }
        return;
    }
    for(int i = cur; i > 0; i--){
    	tempnum += powvalue[i];
        tempans.push_back(i);
        dfs(i, cnt+1);
        tempans.pop_back();
        tempnum -= powvalue[i];
    }
}
int main(){
    cin>>n>>k>>p;
    for(int i = 1; i <= n; i++){
        powvalue[i] = pow(i,p);
        if(powvalue[i] > n){
            powvalue.resize(i);
            dfs(i-1,0);
            break;
        }
        else if(i == n)
        	dfs(i,0);
    }
    if(ans.size() == 0)
        printf("Impossible");
    else{
        printf("%d = %d^%d",n,ans[0],p);
        for(int i = 1; i < ans.size(); i++)
            printf(" + %d^%d",ans[i],p);
    }
}
           

本题有点想不通的是从上界遍历比从下届遍历快200ms，从cur等于1开始遍历，很容易超时。个人思考：可能因为从上界开始遍历，DFS本身的剪枝也相当于把for循环进行了剪枝，而从下界开始遍历，for循环还需要判断一下，是不是需要break（如果不判断直接超时）

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int n, k, p, maxn = -1;
vector<int>num(405), ans, tempans;
void dfs(int cur, int sum){
	if(sum > n || tempans.size() > k)
		return; 
	if(sum == n && tempans.size() == k){
		int tempmaxn = 0;
		for(int i = 0; i < k; ++ i)
			tempmaxn += tempans[i];
		if(tempmaxn >= maxn){
			maxn = tempmaxn;
			ans = tempans;
		}
		return;	
	}
	for(int i = cur; i < num.size(); ++ i){
	  int temp = sum + num[i];
	  if(temp > n)
	    break;
		tempans.push_back(i);
		dfs(i, temp);
		tempans.pop_back();
	}
}
int main(){
	scanf("%d %d %d", &n, &k, &p);
	for(int i = 1; i < 405; ++ i){
		int temp = pow(i, p);
		if(temp > n){
			num.resize(i);
			break;
		}	
		num[i] = temp;
	}
	dfs(1, 0);
	if(ans.size() == 0)
		printf("Impossible");
	else{
		printf("%d = %d^%d", n, ans[k - 1], p);
		for(int i = k - 2; i >= 0; -- i)
			printf(" + %d^%d", ans[i], p);
	}
}