PTA A_1103 Integer Factorization

798236606

传送门：https://pintia.cn/problem-sets/994805342720868352/problems/994805364711604224

解：
1.深度优先遍历

1. #include<cstdio>
   
2. #include<vector>
   
3. #include<cmath>
   
4. 
   
5. using namespace std;
   
6. 
   
7. int n, k, p, maxsum = -1;
   
8. vector <int> temp, ans;
   
9. 
   
10. void DFS(int fac, int now, int sum)
    
11. {
    
12.     if (now == n && temp.size() == k)
    
13.     {
    
14.         if (sum > maxsum)
    
15.         {
    
16.             maxsum = sum;
    
17.             ans = temp;   
    
18.         }
    
19.             
    
20.         return;
    
21.     }   
    
22.    
    
23.     int num = now + (int)pow((double)fac, (double)p);
    
24. 
    
25.     if (num <= n && temp.size() < k)
    
26.     {   
    
27.         temp.push_back(fac);
    
28.         DFS(fac, num, sum + fac);
    
29.         temp.pop_back();
    
30.     }
    
31.         
    
32.     if (fac > 1)
    
33.         DFS(fac - 1, now, sum);
    
34. }
    
35. 
    
36. int main(void)
    
37. {
    
38.     scanf("%d %d %d", &n, &k, &p);
    
39.    
    
40.     DFS(20, 0, 0);//观察到n<=400且p >=2, 则最大的因数为20。
    
41. 
    
42.     if (ans.size())
    
43.     {
    
44.         printf("%d = ", n);
    
45.         for (int i = 0; i < ans.size(); i++)
    
46.         {
    
47.             printf("%d^%d", ans[i], p);
    
48.             
    
49.             if (i < ans.size() - 1)
    
50.                 printf(" + ");
    
51.         }        
    
52.     }
    
53.     else
    
54.         puts("Impossible");
    
55.       
    
56.     return 0;   
    
57. }

复制代码

2.深度优先遍历 + 因数优化

1. #include<cstdio>
   
2. #include<vector>
   
3. #include<cmath>
   
4. 
   
5. using namespace std;
   
6. 
   
7. int n, k, p, maxsum = -1;
   
8. vector <int> temp, ans, fac;
   
9. 
   
10. void DFS(int index, int now, int sum)
    
11. {
    
12.     if (now == n && temp.size() == k)
    
13.     {
    
14.         if (sum > maxsum)
    
15.         {
    
16.             maxsum = sum;
    
17.             ans = temp;   
    
18.         }
    
19.             
    
20.         return;
    
21.     }   
    
22.    
    
23.     int num = now + fac[index];
    
24. 
    
25.     if (num <= n && temp.size() < k)
    
26.     {   
    
27.         temp.push_back(index);
    
28.         DFS(index, num, sum + index);
    
29.         temp.pop_back();
    
30.     }
    
31.         
    
32.     if (index > 1)
    
33.         DFS(index - 1, now, sum);
    
34. }
    
35. 
    
36. int main(void)
    
37. {
    
38.     scanf("%d %d %d", &n, &k, &p);
    
39.    
    
40.     for(int i = 0; (int)pow((double)i, (double)p) <= n; i++)//直接算出所有可能的因数，存储在fac数组        
    
41.         fac.push_back((int)pow((double)i, (double)p));
    
42.    
    
43.     DFS(fac.size() - 1, 0, 0);
    
44. 
    
45.     if (ans.size())
    
46.     {
    
47.         printf("%d = ", n);
    
48.         for (int i = 0; i < ans.size(); i++)
    
49.         {
    
50.             printf("%d^%d", ans[i], p);
    
51.             
    
52.             if (i < ans.size() - 1)
    
53.                 printf(" + ");
    
54.         }        
    
55.     }
    
56.     else
    
57.         puts("Impossible");
    
58.       
    
59.     return 0;   
    
60. }

复制代码