PAT 1103

题目 ： Integer Factorization

分值 ： 30
难度 ： 难题
思路 ： Dfs深搜+剪枝
坑点 ： 你在构造初始数组时,要考虑到==N的情况

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
#include <math.h>
using namespace std ;
vector<int> db ;
vector<int> ans;
vector<int> temp_ans ;
int N , k ,t , max_sum=-1 ;
void init(int x)
{
    int i = 0;
    while(pow(i,x) <= N )
    {
        db.push_back( pow(i,x) );
        i++;
    }
}
void Dfs(int start , int sum_of_factors ,int cnt , int target )
{
    for(int i = start ; i > 0 ; i--)
    {
        if(db[i] > target) continue ;
        if(cnt > k || cnt==k && target != db[i] ) return ;  //次数剪枝
        if(db[i] < target)
        {
            temp_ans[cnt-1] = i ;
            Dfs(i, sum_of_factors+i ,cnt+1 , target- db[i] ) ;
        }
        if(db[i] == target && cnt==k )
        {
            temp_ans[cnt-1] = i ;
            if( max_sum < sum_of_factors+i )
            {
                max_sum = sum_of_factors+i;
                ans = temp_ans;
            }
            return ;
        }
    }
    return ;
}

int main() {
    scanf("%d%d%d",&N,&k,&t);
    init(t);
    int sum = 0 ;
    temp_ans.resize(k+1) ;
    Dfs(db.size()-1,0,1,N);
    if(max_sum == -1)
        printf("Impossible\n");
    else
    {
        printf("%d = %d^%d",N,ans[0],t);
        for(int i = 1; i<k; i++)
            printf(" + %d^%d" , ans[i], t);
    }

}