【PAT】1103. Integer Factorization (30)
2714 단어 DFSpat거슬러 올라가 가지를 자르다.
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
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
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 + 가지치기. http://blog.csdn.net/xyt8023y/article/details/48465993
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int N, K, P;
vector<int> finalFactor;
long sum = 0;
bool dfs(int n, int cur, vector<int> &factor ){
if(cur == K){
// k
if(n == 0){
// N
int tmpSum = 0;
for(int i=0; i<factor.size(); i++){
tmpSum += factor[i];
}
if(tmpSum >= sum){
finalFactor = factor;
sum = tmpSum;
}
return true;
}else{
return false;
}
}
int higher = sqrt(n);
int lower = cur>0? factor[cur-1]:1;
for(int i=lower; i<=higher; i++){
long tmp = pow(i,P);
if(tmp > n){
return false;
}else{
factor[cur] = i;
dfs(n-tmp, cur+1, factor);
}
}
return true;
}
int main(int argc, char** argv) {
scanf("%d%d%d",&N,&K,&P);
vector<int> factor(K);
dfs(N,0,factor);
if(finalFactor.size() == 0){
printf("Impossible
");
return 0;
}
printf("%d = ",N);
for(int i=finalFactor.size()-1; i>=0; i--){
if(i!=0)
printf("%d^%d + ",finalFactor[i],P);
else
printf("%d^%d
",finalFactor[i],P);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ] 5568 카드 놓기아이디어 Level이 0일 때, 즉 아직 카드를 고르지 않았을 때 StringBuilder를 생성하고 sb에 고른 카드를 담도록 하였다. 이후 해당 노드 탐색을 종료하면 sb에 담은 카드를 삭제해 주었다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
