【PAT】A1103 Integer Factorization (30分)

题目

解决

思路

• 题目要求：将n写成k个x^p的和的形式，x递减排列，要求答案中x的和最大,序列字典序最大
• 由于p在一个case里面是固定的，可以用数组记录单词case中所有不超过N的x^p;下标index对应x
• DFS：index, nowK, sum, facSum
• 注意：为了保证字典序大的序列优先被选中，index从到小遍历。
• 递归结束条件：sum == n && nowK == k

实现

Code1

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n, k, p, maxFacSum = -1; 
vector<int> fac, ans, temp;

int power(int x){
	int ans = 1;
	for(int i=0; i<p; i++){
		ans *= x;
	}
	return ans;
}

void init(){
	int i=0, temp = 0;
	while(temp <= n){
		fac.push_back(temp);
		temp = power(++i);
	}	
}

void DFS(int index, int nowK, int sum, int facSum){
	if(sum == n && nowK == k){
		if(facSum > maxFacSum){
			ans = temp;
			maxFacSum = facSum;
		}
		return;
	}
	if(sum>n || nowK>k) return;
	if(index-1 >= 0){
		temp.push_back(index);
		DFS(index, nowK+1, sum+fac[index], facSum+index);	//选分支 
		temp.pop_back();
		DFS(index-1, nowK, sum, facSum);	//不选分支 
	}
}

int main(){
	scanf("%d%d%d", &n, &k, &p);
	init();
	DFS(fac.size()-1, 0, 0, 0);
	if(maxFacSum == -1) printf("Impossible\n");
	else{
		printf("%d = %d^%d", n, ans[0], p);
		for(int i=1; i<ans.size(); i++){
			printf(" + %d^%d", ans[i], p);
		}
	} 
	return 0;	
}