PAT甲级1103 Integer Factorization【dfs】【剪枝】

题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805364711604224

题意：

给定一个数n，要求从1~n中找出k个数，使得这些数的p次方之和等于n

思路：

因为n为400，所以dfs加剪枝【本来还在想dp来着】

他要求输出的方案是数字之和最大的，如果之和相等要输出字典序较大的。

所以还需维护一个数字之和。

一个剪枝的方法是从大到小进行dfs，后面被选的数一定比前面被选的要小，这里不限制的话显然会出现重复。

如果从大到小进行dfs的话，tmpsum=anssum的时候，后面的方案一定不如前面的方案，所以这里不取等号

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<map>
 4 #include<set>
 5 #include<iostream>
 6 #include<cstring>
 7 #include<algorithm>
 8 #include<vector>
 9 #include<cmath> 
10 #include<stack>
11 #include<queue>
12 
13 #define inf 0x7fffffff
14 using namespace std;
15 typedef long long LL;
16 typedef pair<string, string> pr;
17 
18 int n, k, p; 
19 vector<int>ans, tmp;
20 int anssum = 0, tmpsum = 0;
21 
22 int ppow[405];
23 
24 void init()
25 {
26     for(int i = 1; i <= n; i++){
27         ppow[i] = pow(i, p);
28     }
29 }
30 
31 void dfs(int i, int num, int sum)
32 {
33     if(num == 0){
34         if(sum == 0 && tmpsum > anssum){
35             anssum = tmpsum;
36             ans = tmp;
37         }
38         return;
39     }
40     if(sum < 0)return;
41     
42     for(int j = i; j >= 1; j--){
43         tmp.push_back(j);
44         tmpsum += j;
45         dfs(j, num - 1, sum - ppow[j]);
46         tmp.pop_back();
47         tmpsum -= j;
48     }
49 }
50 
51 
52 int main()
53 {
54     scanf("%d%d%d", &n, &k, &p);
55     init();
56     dfs(n, k, n);
57     //printf("%d
", ans.size());
58     if(ans.size() != k){
59         printf("Impossible
");
60     }
61     else{
62         
63         printf("%d = %d^%d", n, ans[0], p);
64         for(int i = 1; i < k; i++){
65             printf(" + %d^%d", ans[i], p);
66         }    
67         printf("
");
68     }
69     return 0;
70 }