1103. Integer Factorization (30) [재 귀적 + 가지치기]

1. 원제: https://www.patest.cn/contests/pat-a-practise/1103
2. 사고방식:
제목:
하나의 수가 N 개의 인자 로 분 해 될 수 있 는 지 를 판단 하 는 p 제곱 의 합.
만약, 가장 큰 N 개의 인자 와.
같은 최대 와 출력 이 비교적 큰 그 서열 이 여러 개 있다.예 를 들 어 1) 1, 2, 3, 5.
2） 1, 2, 4, 4
두 번 째 종 류 를 출력 합 니 다.
가지치기 문제.
생각:
제목 의 뜻 은 그리 어렵 지 않 지만, 어떻게 적합 한 알고리즘 으로 바 꿉 니까?
먼저 폭력 적 으로 해결 하 는 방식 을 생각 할 것 이다. 왜냐하면 x < = 400 이면 인자 가 최대 20 이다.
그 러 니 1 ~ 20 개 씩 해 보 세 요.이런 사고방식 이 옳다.
우 리 는 최적화 할 수 있다.N 개의 인자 이기 때문에 N 개 를 초과 하면 더 이상 판단 할 필요 가 없다.
옮 겨 다 니 는 과정 에서 우 리 는 최소 치 1 부터 테스트 를 시작 하 는 동시에 인자 와 더 크 거나 같은 것 을 만나면 모두 업데이트 합 니 다.
이렇게 하면 문제 중의 여러 개의 똑 같은 상황 을 만족 시 킬 수 있다.
사고방식 을 정리 하면 귀속 + 가지치기 최적화 알고리즘 이다.
즉, 현재 요소 값 x 는 인자 i 를 하나의 것 으로 합 니 다. 그러면 새로운 x = x - i ^ p 는 인자 i 를 용기 factor 에 넣 습 니 다.
이 어 새로운 x 를 재 귀적 으로 옮 겨 다 녔 습 니 다. 이때 의 옮 겨 다 니 는 인 자 는 i 에서 시작 되 었 습 니 다. (앞의 것 이 재 귀적 으로 처리 되 었 기 때 문 입 니 다)
재 귀 완료 후 출력 결과 가 나 왔 으 면 좋 겠 습 니 다.
AC
3. 소스 코드:

#include
#include
#include//  sort    ，pow    
#include//        greater   
using namespace std;

int x, N, p;//        ，        
int maxsum = -1, cur_sum = 0;//          ，     
vector factor, result;//                  
void dfs(int x, int cnt);//    
void print();//    

int main(void)
{
	//freopen("in.txt", "r", stdin);
	cin >> x >> N >> p;
	factor.resize(N);
	dfs(x, 0);//      ，      ，       。N   ，   0~N-1

	if (maxsum == -1)//     
		cout << "Impossible
";
	else
		print();

	return 0;
}

void dfs(int x, int cnt)//      ，      ，       。N   ，   0~N-1
{
	if (cnt == N && x != 0)//    ，   N   ，         
		return;
	if (x < 0)//    ，      。    
		return;

	if (x == 0 && cnt == N)//    N   ，  
	{
		cur_sum = 0;//   
		for (int i = 0; i < N; i++)
			cur_sum += factor[i];

		if (cur_sum >= maxsum)//     ，     ，            
		{
			maxsum = cur_sum;
			result = factor;//         
		}
		return;
	}

	int start = cnt > 0 ? factor[cnt - 1] : 1;//    ，        ，    1  。         
	int end = (int)sqrt(double(x));//    
	for (int fac = start; fac <= end; fac++)//             
	{
		factor[cnt] = fac;//         
		dfs(x - (int)pow(fac, p), cnt + 1);
	}

	return;
}

void print()//  
{
	sort(result.begin(), result.end(), greater());
	printf("%d = ", x);

	for (int i = 0; i < result.size(); i++)
	{
		if (i != 0)
			printf(" + ");
		printf("%d^%d", result[i], p);
	}
	printf("
");
}